화투의 개발 블로그

[문제 링크]

0과 1로되어있는 데이터를 쿼드트리로 압축하는 문제이다.

문제 해결 방법은 다양한데, 분할 정복으로 푼다는 점에선 모두 일치한다.

해결방법 중 하나는 그냥 전부 분할해서, 반환 받은 값이 모두 일치하면 하나로 출력하고, 다르면 나눠 출력하는 방법이 있고.

또 하나는 검사해 나가면서 하나라도 다른 값이 있으면 분할하는 방법이 있다.

나는 두 번째 방법으로 해결하였다. 밑은 이를 구현한 코드이다.

#include <cstdio>
int N, input[64][64];
void quadTree(int x, int y, int size) {
    int cur = input[y][x];
    bool flag = true;
    for (int i = y; (i< y + size) && flag; i++) 
        for (int j = x; (j<x + size) && flag; j++) 
            if (cur != input[i][j]) flag = false;
    //전부 일치했으면 초기 문자 출력 
    if (flag) printf("%d", cur);
    //아니면 4개로 분할한다. 
    else {
        printf("(");
        quadTree(x, y, size / 2);
        quadTree(x + size / 2, y, size / 2);
        quadTree(x, y + size / 2, size / 2);
        quadTree(x + size / 2, y + size / 2, size / 2);
        printf(")");
    }
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i< N; i++) 
        for (int j = 0; j < N; j++) 
            scanf("%1d", &input[i][j]);
    quadTree(0, 0, N);
}

[문제 링크]

'문제 조건' 만큼은 명확하게 주어주기 때문에 어렵지 않다. 다만 이걸 코드를 옮기는게 너무 어려웠다.

난 이 문제를 비트마스크와 DP로 풀었다.

(왠만하면 끝까지 비트마스크로 풀고싶었는데 중간에 구슬 액션부분은 머리아파서 그냥 벡터로 변환했다)

이 문제에 구슬이 공간이 16개가 주어지는데, 빈공간(00), 흰색구슬(01), 초록색구술(10)처럼 공간마다 2비트씩 할당해서 

모든 접시의 상태를 unsigned int형으로 표현이 가능하다.

상태공간을 비트마스크로 표현한 뒤에는 문제에 주어진 조건을 따라 가면 된다.

(메모이제이션은 map으로 표현하였다. 표현 공간이 unsigned int형 최대 32비트이기 때문에 배열로는 표현이 어렵고 공간 낭비가 크다.)

#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <vector>
//반복문 매크로
#define FOR(k,a,b) for(int k = a; k<b; k++)
#define M_FOR(k,a,b) for(int k = a; k >= b; k--)
#define D_FOR(a,b,c,d) for(int i = a; i<b; i++) for(int j = c; j<d; j++)
//구슬 비트 
#define W_BIT (8*i+2*j)
using namespace std;
//memoization 
map<unsigned int, double> cache[17];
typedef pair<unsigned int, double> dishStat;
int T, actCount;
unsigned int dish;
char act[17];

//bitmask -> vector 
vector<vector<char> > getStatVector(unsigned int dish) {
    vector< vector<char> > ret;
    ret.resize(4);
    D_FOR(0, 4, 0, 4) {
        if (dish&(1 << W_BIT)) ret[i].push_back('W');
        else if (dish&(1 << (W_BIT+1))) ret[i].push_back('G');
        else ret[i].push_back('E');
    }
    return ret;
}
  
double getProb(int curAct, unsigned int curDish) {
    //기저사례 1 : 모든 액션 실행.
    if(curAct == actCount) return curDish==dish? 1:0;
    //기저사례 2 : DP 
    if (cache[curAct].find(curDish) != cache[curAct].end())
        return cache[curAct][curDish];
    vector<vector<char> > ret = getStatVector(curDish);
        //구슬일 경우
        if (act[curAct] == 'W' || act[curAct] == 'G') {
            int centNum = 0, curBead = act[curAct] == 'W' ? 0 : 1;
            D_FOR(1, 3, 1, 3) if (ret[i][j] == 'E')  centNum++;
            //중앙 공간이 3개 비었을 경우, 대각선 100% 
            if (centNum == 3) {
                if (ret[1][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (20 + curBead)));
                else if (ret[1][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (18 + curBead)));
                else if (ret[2][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (12 + curBead)));
                else if (ret[2][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (10 + curBead)));
            }
            //중앙 공간이 1,2,4개 남았을경우, 1/centNum 
            else if (centNum <= 4 && centNum > 0) {
                D_FOR(1, 3, 1, 3) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (W_BIT + curBead))) / centNum;
                }
            }
            //중앙이 꽉찼을 경우, 1/나머지공간 
            else {
                D_FOR(0, 4, 0, 4) if (ret[i][j] == 'E') centNum++;
                D_FOR(0, 4, 0, 4) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += (getProb(curAct + 1, curDish | (1 << (W_BIT + curBead)))) / centNum;
                }
  
            }
        }
        //나머지 액션 
        else {
            unsigned int nextDish = curDish;
            if (act[curAct] == 'L') {
                FOR(k,0, 4) D_FOR(0, 4, 1, 4) { 
                    //직전 -1~-2비트가 00이면 오른쪽으로 2bit shift 
                    if (!(nextDish &(3 << (W_BIT - 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'R') {
                FOR(k,0, 4) FOR(i,0,4) M_FOR(j,2,0) {
                    //이후 1~2비트가 00이면 왼쪽으로 2bit shift  
                    if (!(nextDish &(3 << (W_BIT + 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'T') {
                FOR(k,0, 4) D_FOR(1,4,0,4) {
                    //이전 -7~-8비트가 00이면 왼쪽으로 8bit shift 

                    if (!(nextDish &(3 << (W_BIT - 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
              
            else if (act[curAct] == 'B') {
                FOR(k,0, 4) M_FOR(i,2,0) FOR(j,0,4){
                    //이후 7~8비트가 00이면 왼쪽으로 8bit shift 
                    if (!(nextDish &(3 << (W_BIT + 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
        }    
   return cache[curAct][curDish];
}
 
int main() {
    cin >> T;
    while (T--) {
        dish = 0;
        cin >> actCount;
        FOR(k, 0, actCount) cin >> act[k];
        D_FOR(0, 4, 0, 4) {
            char tmp;
            cin >> tmp;
            if (tmp == 'W') dish |= 1 << W_BIT;
            if (tmp == 'G') dish |= 1 << (W_BIT+1);
        }
        cache[actCount][dish] = 1.0;
        printf("%.9lf\n", getProb(0, 0));
        FOR(k, 0, 17)cache[k].clear();
    }
}

[문제 링크]

짝 괄호를 지우는 모든 경우의 수를 구하는 문제이다.

처음엔 반복문으로 시도하고자 했으나 총 경우의 수인 2^(괄호 짝의 갯수)를 반복문으로 어떻게 표현할지 감이 오질않아서.

재귀로 해결하였다.

먼저 문자열을 한번 순회하며 스택을 이용해 짝괄호의 인덱스를 저장한다.

이렇게 저장한 인덱스들을 이용해서 문자열을 하나하나 완성해 나가면 된다.

문자열을 만들어 나가는데 가능한 경우의 수는 다음과 같다.

 가능한 경우의 수

 1. 현재 문자가 괄호일경우 : (1) 괄호를 지운다, (2) 괄호를 지우지 않는다.

 2. 현재 문자가 괄호가 아닐 경우 : 문자를 붙이고 문자열을 만들어간다.

여는 괄호가 나왔을 때, 짝 괄호에 괄호를 지웠다고 체크하고, 문자열을 이어 붙인다.

그와 대응되는 짝 괄호가 나타나면 그 괄호는 문자열에 포함시키지 않으면 된다.

완성된 문자열은 set에 저장하고, 모든 괄호를 지우지 않을 경우만 set에서 제거한 뒤에 출력하면 된다.

#include <iostream>
#include <string>
#include <set>
#include <stack>
using namespace std;
string input;
int matching[221], brkNum = 0; 
bool erasing[221]; 
set<string> retSet;
string ret;

void eraseBrackets(int cur){
    //기저사례 : 문자열을 완성
    if(cur == input.length()){
        retSet.insert(ret);
        return;
    } 
    if(input[cur] == '('){  
        //괄호를 지우는 경우
        erasing[matching[cur]] = true;
        eraseBrackets(cur+1);   
        erasing[matching[cur]] = false;
    }
    if(input[cur] ==')'&&erasing[cur]){
        //짝괄호를 지운 경우 
        eraseBrackets(cur+1);
    }
    //괄호,짝괄호를 안지우거나 일반 문자열일 경우. 
    else{
        ret+=input[cur];
        eraseBrackets(cur+1);
        ret.resize(ret.size()-1);
    }
}

//괄호 매칭 설정 
void matchBrackets(string& input){
    stack<int> st;
    for(int i = 0; i<input.length();i++){
        if(input[i] == '(') st.push(i);
        else if(input[i] == ')'){
            //매칭이 되는 괄호를 저장한다. 
            matching[i] = st.top();
            matching[st.top()] = i;     
            st.pop();
            brkNum++;
        }
    }
}
int main(){
    cin>>input;
    matchBrackets(input);
    eraseBrackets(0);
    retSet.erase(input);
    set<string>::iterator it;
    for(it = retSet.begin(); it!=retSet.end(); it++)
        cout<<(*it)<<endl;
}

[문제 링크]

Trailing zero의 최적을 구하는 문제다.

Trailing zero는 숫자에 들어있는 0의 갯수를 말하는데, 숫자에 0이 들어가려면 인수로 10을 가지고 있어야 한다.

따라서 소인수분해 시, 2와 5의 짝 만큼 Trailing zero가 추가된다.

이 문제는 소인수 2와 5를 가장 적게 가지는 경로를 찾는 문제이다.

모든 경로에 대해서 소인수 2와 5의 갯수를 전부 메모이제이션 한다.

앞서 설명한 대로 10이 만들어지려면 2와 5가 동시에 필요하므로, 2나 5중 가장 작은 값이 Trailing zero의 최소값이 된다.

지금 위치부터 K만큼 앞에 있는 징검다리를 비교하면서, 소인수 2와 5의 갯수가 최소가 되는 값을 찾아 각각 저장해나가면 구할 수 있다. 

단 주의해야 할 점은 dp를 할때 재귀(top-down)를 쓰면 시간초과가 발생한다.(연산 갯수가 총 10만개이다.)

이 문제는 반복문(bottom-up)으로풀어야 해결이 가능하다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_VAL 987654321;
int T, N, K, S[100001], cache[100001][2];
int getPf(int div,int input){
    int ret = 0;
    while(input%div == 0){
        ret++;
        input /=div;
    }
    return ret;
}
void stepping_stone(){
    cache[0][0] = getPf(2,S[0]);
    cache[0][1] = getPf(5,S[0]);
    for(int cur = 1; cur<N; cur++){
        cache[cur][0] = MAX_VAL;
        cache[cur][1] = MAX_VAL;
        for(int j=1;j<=K;j++){
            int prev = cur-j;
            if(prev >= 0){
                cache[cur][0] = std::min(cache[cur][0],cache[prev][0] + getPf(2,S[cur]));
                cache[cur][1] = std::min(cache[cur][1],cache[prev][1] + getPf(5,S[cur]));
            }
        }
    }
    printf("%d\n",std::min(cache[N-1][0],cache[N-1][1]));
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&N,&K);
        for(int i = 0; i<N; i++)
            scanf("%d",&S[i]);
        stepping_stone();
    }
}

[문제 링크]

이전 Coder's high 제출 문제다.

어려운 문제는 아니고 그냥 조건만 맞추면 되는 문제인데, 자꾸 조건을 중간에 빼먹어서 문제였다.

처음엔 그냥 월별, 요일별로 조건문에 때려넣어서 했는데 코드가 너무 안예뻐서... 그냥 다 상수처리해서 정리하였다.

#include <iostream>
#include <string>
using namespace std;
int testcase;
const int monthEnd[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
const int monthBefore[12] = {31,31,28,31,30,31,30,31,31,30,31,30};
const string dowArr[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
int main(){
    cin>>testcase;
    while(testcase--){
        int cur,m,d,dowIdx;
        string dow;
        cin>>m>>d>>dow;
        for(int i = 0;i<7;i++){
            if(!dow.compare(dowArr[i])){
                dowIdx = i;
                break;
            }
        }   
        for(int i = 0; i < 7; i++){
            cur = d-(dowIdx-i);
            cur = cur<1?monthBefore[m-1] + cur : (cur>monthEnd[m-1]?cur-monthEnd[m-1]:cur);
            printf("%d ",cur);
        }
        printf("\n");
    }
} 

[문제 링크]

예전 Coder's high 제출 문제라고 한다. 처음에 기하 문제인 줄 알고 머리를 싸맸지만 알고보니 정말 간단한 문제였다.

각 고기 별로만 뒤집을 생각만 하고 있었는데.

그냥 고기판 전체를 뒤집으면 모든 고기가 뒤집힌다. (약간 낚시성 문제인거같다.. 예제 출력부터가... 물론 조건에 모든 경우는 다 가능하다고 설명하긴 했다만...)

#include <cstdio>
int testcase,H,W;
char Grill[11][11],output[11][11];
int main(){
    scanf("%d",&testcase);
    while(testcase--){
        scanf("%d %d",&H,&W);
        for(int height = 0; height<H; height++){
            getchar();
            for(int width = 0; width < W; width++){
                scanf("%c",&Grill[height][width]);
            }
            for(int width = W-1; width>=0; width--){
                printf("%c",Grill[height][width]);
            }
            printf("\n");
        }
    }
    
}

[문제 링크]

DFS 문제다. 각 방이 노드, 문이 간선인 무방향 그래프로 보고 DFS로 방문하며 출력을 하면 된다.

나는 인접리스트로 문제를 풀었는데,(인접배열로 하기엔 배열의 크기가 너무 크다.)

가장 낮은 번호의 방을 먼저 방문한다고 했으므로, 인접리스트를 정렬 한 뒤에 탐색을 진행하도록 하였다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m;
vector<vector<int> > graph;
vector<int> visited;
void dfs(int cur){
    printf("%d ",cur);
    sort(graph[cur-1].begin(),graph[cur-1].end());
    for(int i =0; i<graph[cur-1].size();i++){
        if(visited[graph[cur-1][i]-1]==0){
            visited[graph[cur-1][i]-1] = 1;
            dfs(graph[cur-1][i]);
        }
    }
}
int main(){
    scanf("%d %d",&n,&m);
    graph.resize(n);
    visited.resize(n);
    for(int i = 0; i < m; i++){
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a-1].push_back(b);
        graph[b-1].push_back(a);
    }
    visited[0] = 1;
    dfs(1); 
}

[문제 링크]

DP 문제이다. DP와 그리디 문제 예시로 유명한 '배낭 채우기'문제와 정말 유사한 문제이다.

배낭 채우기 문제와는 다른점은 메모이제이션 할 값이 실수형이라는 점인데, 여기서 소수 둘째자리까지만이라는 제한을 주었으므로,

이는 100을 곱해 자연수로 만든 후 처리가 가능하다.

다만 실수 자료형 부동소수점 문제로 오차가 있을 수 있으니 100을 곱한뒤 소수 첫째 자리에서 반올림해주어야 한다.

그렇게 변형한 금액으로 메모이제이션해 최대 값을 구하면 된다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
int n, c, cache[10001];
double m, p;
typedef pair<int, int> Candy;
Candy cd[5001];
int candyStore(int money) {
    int& ret = cache[money];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i <n; i++) {
        //남은 금액이 0 이상일 경우에만 비교. 
        if (money - cd[i].second >= 0) {
            int tmp = cd[i].first + candyStore(money - cd[i].second);
            ret = max(ret, tmp);
        }
    }
    return ret;
}
int main() {
    while (true) {
        memset(cache, -1, sizeof(cache));
        scanf("%d %lf", &n, &m);
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d %lf", &c, &p);
            cd[i] = make_pair(c, (int)(p*100+0.5));
        }
        printf("%d\n", candyStore((int)(m*100+0.5)));
    }
}