개발 블로그

문제 링크 : www.acmicpc.net/problem/13549

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

접근 방법

숨바꼭질 4 문제(nanyoungkim.tistory.com/75)와 비슷했지만 순간이동은 0초, 걷는건 1초로 가중치가 달랐기 때문에 덱을 이용했다.

순간이동은 0초가 걸리니까 앞에서 push 하고,

걷는건 1초가 걸리니까 뒤에서 push 했다.

(덱에는 pair<int 시간, int 위치> 를 저장했다. -> 시간에 따른 우선순위를 위해 첫번째 요소에 시간을 저장한 것임.)

주의할 점

아무 생각 없이 숨바꼭질4 문제와 같이 if 조건문 순서를 "뒤->앞->순간이동" 으로 해서 계속 7%에서 '틀렸습니다' 메세지가 출력됐다. push_front(), push_back()으로 구분을 해줬더라도 순간이동이 뒤/앞 이동보다 더 먼저 push 되어야한다!!

#include <iostream>
#include <deque>
#include <utility>

using namespace std;

int N, K;
int visited[100001] = {0};

int ans=0;

void BFS(){
    
    deque<pair<int,int>> que;
    que.push_back(make_pair(0,N));
    visited[N] = 1;
    
    while(!que.empty()){
        int nowTime = que.front().first;
        int nowLoc = que.front().second;
        que.pop_front();
        
        if(nowLoc==K){
            ans = nowTime;
            return;
        }
        
        //순간이동 -> 앞/뒤 이동보다 먼저 써줘야한다.
        if(!visited[2*nowLoc] && 0<=2*nowLoc && 2*nowLoc<=100000){
            visited[2*nowLoc] = 1;
            que.push_front(make_pair(nowTime, 2*nowLoc));
        }
        //뒤로 이동
        if(!visited[nowLoc-1] && 0<=nowLoc-1 && nowLoc-1<=100000){
            visited[nowLoc-1] = 1;
            que.push_back(make_pair(nowTime+1,nowLoc-1));
        }//앞으로 이동
        if(!visited[nowLoc+1] && 0<=nowLoc+1 && nowLoc+1<=100000){
            visited[nowLoc+1] = 1;
            que.push_back(make_pair(nowTime+1, nowLoc+1));

        }
    }
}


int main(){
    
    cin >> N >> K;
    BFS();
    cout << ans ;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/13913

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

접근 방법

BFS로 한 스템씩 나아가면서 visited[]에 직전에 지났던 위치를 저장한다. 

visited[]는 처음에 시작점을 제외하고 -1로 초기화 시켰기 때문에 위치를 지정하면 동시에 방문여부도 체크할 수 있다.

stop 조건에 걸리면 visited[] 를 거꾸로 타고 올라가면서 지나온 자리를 resVec에 push 한다.

그리고 main()에서 resVec을 거꾸로 출력한다.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

int N, K;
int visited[100001];
queue<int> que;
vector<int> resVec;

void BFS(){
    
    que.push(N);
    
    while(!que.empty()){
        
        int now = que.front();
        que.pop();
        
        if(now==K){
            resVec.push_back(now);
            while(visited[now]!=100001){		   //처음 시작점까지 갈 때 까지
                resVec.push_back(visited[now]);   //거꾸로 타고 올라가면서 지나온 자리 push
                now = visited[now];
            }
            return;
        }
        
        
        if(visited[now-1]==-1 && 0<=now-1 && now-1<=100000){	//방문체크 and 범위체크
            visited[now-1] = now;		//바로 직전에 지나온 자리 저장
            que.push(now-1);			
        }
        if(visited[now+1]==-1 && 0<=now+1 && now+1<=100000){
            visited[now+1] = now;
            que.push(now+1);
        }
        if(visited[2*now]==-1 && 0<=2*now && 2*now <= 100000){
            visited[2*now] = now;
            que.push(2*now);
        }
    } 
}

int main(){
   
    cin >> N >> K;
    memset(visited, -1, sizeof(visited));
    visited[N] = 100001;		//시작 지점 체크를 위함
    
    BFS();
    cout << resVec.size()-1 << "\n";
    
    for(int i = resVec.size()-1; i>=0; i--){
        printf("%d ", resVec[i]);
    }
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14226

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

접근 방법

처음 시작 조건(이모티콘 1개, 시간 0초, 클립보드 0개)에서 시작해서 각각 연산을 수행한 뒤 상태를 Queue에 push 한다.

여기서 주의할 점은 방문 여부를 체크하는 visit 배열이 이차원 배열이라는 것이다.

visit[i][j] 는 화면에 i개 이모티콘이 있고 클립보드에 j개 이모티콘이 있는 상태이다. 

처음에  '시간이 더 나중인게 이모티콘 글자 수가 더 큰 경우' 에는 ?

이라는 의문이 들었는데, 

whlie문 한 번 돌 때마다

if(s==S)인지 체크하고 / 1초씩 순차적으로 증가하기 때문에

if(s==S)이 만족해서 반복문이 멈출 때가 바로 시간의 최소값이다. 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

int S;
int visit[1001][1001];
int ans;

void BFS(){
    //임티개수,              초, 클립보드 안의 수
    queue<pair<int, pair<int,int>>> que;
    que.push(make_pair(1, make_pair(0,0)));
    visit[1][0] = 1;

    while(!que.empty()){
          
        int s = que.front().first;
        int sec = que.front().second.first;
        int clip = que.front().second.second;
        que.pop();
        
       // cout << s<<"개 / " << sec<<"초  /  " << clip<<"클립보드\n";
       
        if(s==S) {
            ans = sec;
            return;
        }
        
        if(s>0 && s<=1000){
            //복사
            if(visit[s][s]==0){
                visit[s][s] = 1;
                que.push(make_pair(s, make_pair(sec+1, s)));
            }
            
            //하나 삭제
            if(visit[s-1][clip] == 0){
                visit[s-1][clip] = 1;
                que.push(make_pair(s-1, make_pair(sec+1, clip)));
            }
        }
        
        //붙여넣기
        if(clip>0 && s+clip<=1000){
            if(visit[s+clip][clip]==0){
                visit[s+clip][clip] = 1;
                que.push(make_pair(s+clip, make_pair(sec+1, clip)));
            }
        }
    }
}


int main(){

    cin >> S;

    for(int i = 0; i<=1000; i++){
        for(int j = 0; j<=1000; j++){
            visit[i][j] = 0;
        }
    }
    
    BFS();
    cout << ans;

    return 0;
}

문제 링크 : www.acmicpc.net/problem/1261

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

접근 방법

visit[][]로 방문 여부를 체크해야하나 싶었는데, 그렇게 하면 나중에 방문한 경우가 더 적게 벽을 부신 경우가 될 수 있기 때문에 다른 방법을 고려해야 했다.

즉, 다음 방문할 칸이 벽이던 방이던, 갱신 조건(더 적게 벽을 부신 경우)을 만족할 경우에만 Queue에 push 해주면 된다. 그러면 마지막에 cntWall[N][M]에서 상하좌우로 탐색을 할 때 범위체크에서 우/하 방향이 걸러지고 상/좌의 경우에는 갱신조건을 만족하지 못하므로(cntWall가 같으므로) 더이상 Queue 에 Push 하지 않고 while문을 벗어나게 된다. 

(while문 안에 if 조건문으로 탈출 조건을 따로 안 써줘도 된다.)

주의할 점

처음에 메모리 초과가 난 이유가 Queue에 너무 많은 원소가 들어가서였다. 그 코드에서는 범위 체크만 통과하면 바로 Queue에 next 칸을 push 했었다. 

수정된 아래의 코드처럼 갱신 조건을 만족할 때만 Queue 에 push 해주면 메모리초과가 안 뜬다.

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

#define MAX 101

int N,M;
int map[MAX][MAX];
queue<pair<int,int>> que;

int cntWall[MAX][MAX];

//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

void BFS(){
    
    while(!que.empty()){

        int r = que.front().first;
        int c = que.front().second;
        que.pop();
        
        for(int i = 0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr<1 || nr>N || nc<1 || nc>M) continue;		//범위 체크
	
            if(map[nr][nc] == 1){		//다음 칸이 벽일 때
                
                if(cntWall[nr][nc] > cntWall[r][c]+1){		//갱신 조건
                    cntWall[nr][nc] =cntWall[r][c]+1;
                     que.push(make_pair(nr,nc));
                }
                
            }
            else{						//다음 칸이 방일 때
                if(cntWall[nr][nc]>cntWall[r][c]){			//갱신 조건
                    cntWall[nr][nc] = cntWall[r][c];
                    que.push(make_pair(nr,nc));
                }
            }
        }
    }
}

int main(){

    cin >> M >> N;
    string str;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            cntWall[i][j] = 1000;			//최대 값으로 초기 설정
        }
    }
    
    for(int i = 1; i<=N; i++){
        cin >> str;
        for(int j = 1; j<=str.length(); j++){
            map[i][j] = str[j-1]-'0';
        }
    }
    //입력받을 때 동일한 방법
    /* for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            scanf( "%1d", &map[i][j] );
        }
    }*/
   
    
    que.push(make_pair(1,1));
    cntWall[1][1] = 0;          //항상 뚫려 있다고 했으므로 0으로 초기 설정 가능
    
    BFS();
    
    cout << cntWall[N][M];
   
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1707

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

접근 방법

연결 그래프와 비연결 그래프 두 경우를 생각해야한다.

1번노드부터 V번노드까지 BFS를 돌린다. 그래야 연결되지 않고 따로 떨여져 있는 노드도 처리할 수 있다.

처음 시작노드를 team1로 정했으면 그 노드와 연결된 노드들은 team2로, 그 다음은 다시 team1로 지정한다.

지정이 끝나면 이중포문을 돌면서 아래와 같이 검사한다. 

for(1번노드부터 V번 노드까지){

  for(해당 노드에 연결된 모든 노드들에 대해){   ...   } 

}

문제의 테스트케이스는 모두 연결 그래프로 나와있어서 비연결 그래프에 대해 생각해야한다는게 어려웠는데 백준 질의응답을 보고 해결했다.

예를 들어,

1-2

3-4

이렇게 연결되어 있는 그래프가 있다고 하자.

{1,4} ,{2,4} 또는 {1,3},{2,4} 로 집합을 나눌 수 있으므로 답은 YES이다.

주의할 점

테스트케이스가 반복되는 경우이므로 테스트케이스가 끝날 때마다 초기화를 해준다.

그리고 출력할 때도 줄바꿈을 해줘야한다.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>    //memset

using namespace std;

vector<int> vecArr[20001];				//벡터1부터 벡터V까지에 대한 벡터배열이므로 +1
vector<pair<int,int>> eVec;

int visit[20001] = {0};
int group[20001] = {0};
int V,E;

void BFS(int start){
    queue<int> que;

    que.push(start); 
    visit[start] = 1;	//방문 체크
    group[start] = 1;	//집합 가르기
    
    int team = 1;
    
    while(!que.empty()){
   
        int sV = que.front();
        que.pop();

		
        //연결된 노드들을 현재벡터(sV)와 반대로 
        if(group[sV]==1) team = 2;
        else if(group[sV]==2) team = 1;
        
        for(int i = 0; i<vecArr[sV].size(); i++){
            
            int nV = vecArr[sV][i];
            
            if(visit[nV]==0){
                que.push(nV);
                visit[nV] = 1; 
                group[nV] = team;         
            }   
        }
    }

}


int main(){
    
    int T; cin >> T;
    
    for(int t=0; t<T; t++){
        
        cin >> V >> E;
        
        int e1,e2;
        for(int i = 0; i<E; i++){
            cin >> e1 >> e2;
           
            vecArr[e1].push_back(e2);
            vecArr[e2].push_back(e1);

        }

        for(int i = 1; i<=V; i++){
            if(visit[i]==0){			//모든 노드에 대해 돌려야 비연결 그래프도 통과
                BFS(i);
            }

        }
        
        
        bool chk = true;
        for(int i=1; i<=V; i++){
            for(int j = 0; j<vecArr[i].size(); j++){
                if(group[i]==group[vecArr[i][j]]){
                    chk=false;
                    break;
                }
            }
        }
       if(!chk) cout << "NO\n";
       else cout << "YES\n";
  
        for(int i = 0; i<=V; i++) vecArr[i].clear();
        memset(visit,0,sizeof(visit));
        memset(group,0,sizeof(group));
        
        
    }
    
    
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14889

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

접근 방법

sumFunc이 DFS이다. 

DFS 돌면서 각각 팀의 능력치를 더한다.

그 능력치의 차를 구해서 최소가 되는 경우를 찾는다.

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int N;
int map[21][21];
int visited[21] = {0};
int num;

vector<int> start;
vector<int> link;

int chk[11] = {0};

vector<int> vec;
vector<int> sumVec;
int ans1 = 0;
int ans2= 0;
int ans = 100000000;


vector<int> sSum;

//DFS 돌면서 팀의 능력치 더함
void sumFunc(int toPick, vector<int> vec){
    
    if(toPick==0){
        
        int sum =  map[sumVec[0]][sumVec[1]] + map[sumVec[1]][sumVec[0]];
        sSum.push_back(sum);
        return;
    }
    
    for(int i = 0; i<vec.size(); i++){
        if(chk[i] ==0){
            chk[i] = 1;
            sumVec.push_back(vec[i]);
            sumFunc(toPick-1, vec);
            sumVec.pop_back();
            chk[i] = 0;
            
        }
    }
    
    
}


void choiceFunc(int toPick, int num){
    
    
    if(toPick==0){
        ans1 = 0; ans2 = 0;
        link.clear();
		
        //스타트와 링크 각각 start, link 벡터에 나눔
        for(int j = 1; j<=N; j++){
            if(visited[j]==0) {
                link.push_back(j);
            }
        }

        //스타트
        sumFunc(2, start);
        for(int i = 0; i<sSum.size(); i++){
            ans1+=sSum[i];
        }
        sSum.clear();
        
        //링크
        sumFunc(2, link);
        for(int i = 0; i<sSum.size(); i++){
            ans2+=sSum[i];
        }
        sSum.clear();


        if(ans1<ans2){		//더 큰게 ans1이 되게 바꿈
            int tmp=ans1;
            ans1=ans2;
            ans2=tmp;
        }
        
        if(ans1-ans2 < ans){ans = ans1-ans2;}	//능력치 차가 최소인 것 구함 
        memset(chk, 0, sizeof(chk));
        
        return;
        
    }
    
    for(int i = 1; i<=N; i++){
        
        if(visited[i]==0 && num<i){
            visited[i] = 1;
            start.push_back(i);
            choiceFunc(toPick-1, i);
            start.pop_back();
            visited[i] = 0;
            
        }
    }
    
}



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=N; j++){
            cin >> map[i][j];
        }
    }

    num = (N*(N-1)) / 4;
    
    choiceFunc(N/2, 0);
    
    cout << ans/2 ;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/14501

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 1일2일3일4일5일6일7일TiPi

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

접근 방법

파라미터 start를 바꿔가며 DFS를 돈다. 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int T[15] = {0};
int P[15] = {0};

int ans = 0;

void dfs(int start, int sum){
    
    if(start>N) return;
    
    ans = max(ans, sum);
    
    for(int i = start; i<N; i++){
        dfs(i+T[i], sum+P[i]);		//시작일을 바꿔가며 최대 sum 체크
    }
        

}


int main(){
    
    cin >> N;
    for(int i = 0; i<N; i++){
        cin>> T[i] >> P[i];
    }
    
    dfs(0,0);
    cout << ans << "\n";
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1759

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근 방법

DFS를 돌면서 ansVec벡터에 알파벳들을 push하고, toPick을 L부터 0까지 감소시켜나간다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<char> alpha;
vector<char> ansVec;
int visited[15] = {0};

//문제 조건 만족하는지 체크 : 모음 최소 1개 포함 and 암호 최소 길이 3
bool chk(){
    int cntV = 0;   //모음
    int cntC = 0;   //자음
    for(int i = 0; i<ansVec.size(); i++){
        if(ansVec[i]=='a' || ansVec[i]=='e' || ansVec[i]=='i' || ansVec[i]=='o' || ansVec[i]=='u') {cntV++;}
        else cntC++;
    }
    if(cntV>=1 && cntC>=2) return true;
    else return false;

}



void dfs(int toPick, char c){
    
    if(toPick==0){
        if(chk()){
            for(int i = 0; i<ansVec.size(); i++){
                cout << ansVec[i];
            }
            cout << "\n";
        }
        return;
    }
    
    
    for(int i = 0; i<alpha.size(); i++){
        
        if(visited[i]==0 && c<=alpha[i]){	//중복가능하니 등호 포함(c<=alpha[i])
            visited[i] = 1;
            ansVec.push_back(alpha[i]);
            dfs(toPick-1, alpha[i]);
            ansVec.pop_back();
            visited[i] = 0;
            
        }
        
    }
    
}
int main(){
    
    int L,C;
    cin >> L >> C;
    
    for(int i = 0; i<C; i++){
        char c; cin >> c;
        alpha.push_back(c);
    }
    
    sort(alpha.begin(), alpha.end());
    dfs(L, 'a');	//암호 알파벳 중복 가능하니까 초기값 'a'로 설정해도 상관 x
    
    
    return 0;
}