개발 블로그

문제 링크 : 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;
}

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

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

접근 방법

map[0][0] ~ map[N-1][N-1] 까지 돌면서 방문하지 않은 곳에서 dfs를 호출한다. 호출하기 전에 cnt를 1로 초기화 한 뒤, dfs 함수 안에서 재귀로 dfs가 재호출 될 때마다 연결된 단지로 전진한 것이므로 cnt를 1씩 증가해준다. 처음에 호출한 dfs가 끝나면 cnt를 cntVec안에 push 해서 마지막에 출력할 수 있도록 저장하고, 단지 그룹 1개를 다 탐색한 것이므로 res를 1 증가시킨다.

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

using namespace std;

int map[25][25];
int visited[25][25];
vector<int> cntVec;

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

void dfs(int r, int c){

    for(int i = 0; i<4; i++){
        
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr>=N || nr<0 || nc>=N || nc<0) continue;
        
        if(visited[nr][nc]==0 && map[nr][nc]==1){   //방문 안했고 집이 있으면
            visited[nr][nc] = 1;                    //방문했다고 표시하고
            cnt+=1;                                 //집 개수 세기
            dfs(nr,nc);
        }
    }
 
}


int main(){
    
    int res=0;
    
    cin >> N;
    string str;
    
    for(int i = 0; i<N; i++){
        cin >> str;
        for(int j = 0; j<str.length(); j++){            //입력 주의
            visited[i][j] = 0;
            
            if(str[j] == '1'){
                map[i][j] = 1;
            }
            else map[i][j] = 0;
        }
    }
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            
            if(map[i][j]==1 && visited[i][j]==0){
                visited[i][j] = 1;
                cnt = 1;                        //처음은 시작점 포함하므로 1로 초기화
                dfs(i,j);
                cntVec.push_back(cnt);
                res++;                          //단지 그룹 1개 탐색 끝남
            }
        }
    }
    
    sort(cntVec.begin(), cntVec.end());
    cout << res << "\n";
    
    for(int i = 0; i<cntVec.size(); i++){
        cout << cntVec[i] << "\n";
    }

    return 0;
}