백준 '단계별로 풀어보기' - 동적 계획법 1 (1)

맨 처음 다이나믹 프로그래밍에 대한 공부를 다시 하고 백준 '단계별로 풀어보기' 카테고리에 있는 '동적 계획법 1'부터 부수자 선언. (TMI .. 동적 계획법 1은 이번 학기에 하다가 몰아치는 6전공의 강의와 과제로 인해 방치되어 있던 단계이다.)

그래서 매일매일 백준 3문제를 풀어서 내 귀여운 백준 티어(아직도 실버 2..)를 올려 보겠다는 이번 방학 내 첫 번째 시스템의 시작으로 디피 문제들을 처음부터 다시 풀어 보겠다고 결정했다. (2번째 TMI ... 저번주에 일정이 너무 많았던 나는 매일 백준 3문제를 거의 지키기 못했다 ... 이번주는 무조건 ..!!)
<0302 추가> 제가 .. 이런 계획을 세웠었나요 ...??

방금 해당 단계 문제들 중 절반을 해결해서, 중간 점검 겸 몇 문제 정도 간단한 코멘트와 함께 복기해 보려 한다.

※ 스포주의 : 제 정답 코드를 아래에 작성해 놓았습니다.
스포를 원하지 않으면 문제 먼저 풀고 코드를 비교해 봅시다!
++ 코드, 알고리즘 훈수는 언제나 환영 ^_^

---

백준 #1094

01 타일

link : https://www.acmicpc.net/problem/1904

#include <iostream>
#include <vector>

std::vector<int> memo;
int a, b;
int res;

int main(void) {
    int N; std::cin>>N;
    
    memo.push_back(0);
    memo.push_back(1);
    memo.push_back(2);
    a = memo[1]; b = memo[2];
    for(int i=3; i<=N; i++) {
        memo.push_back((memo[i-1] + memo[i-2]) % 15746);
    }

    std::cout<<memo[N]<<std::endl;
    
    return 0;
}

• 이건 대체 왜 피보나치일까? 수학적 귀납법으로 피보나치인 듯하다 추측하고, 그렇게 풀어서 맞긴 했으나, 의문 ... (특징: 모르는데 안 찾아봄ㅎ)

• 나머지의 분배 법칙 → 이걸 몰라서 한참을 고생하다가 겨우 풀었다. 이번 학기 확랜 & 공수 둘 다 말아먹은 그의 처참한 수학 실력 ..

---

백준 #9461

파도반 수열

link : https://www.acmicpc.net/problem/9461

#include <iostream>

long arr[101] = {0, };

long P(long N) {
    arr[1] = 1; arr[2] = 1; arr[3] = 1;
    arr[4] = 2; arr[5] = 2;
    
    if (arr[N] != 0) return arr[N];
    else {
        return arr[N] = P(N-1) + P(N-5);
    }
}

int main(void) {
    long T, N;
    
    std::cin>>T;
    for(long i=0; i<T; i++) {
        std::cin>>N;
        std::cout<<P(N)<<std::endl;
    }
    
    return 0;
}

• Top-down 방식! (배열에 결과가 이미 있으면 그 값을 가져다가 쓰고, 결과가 없다면 재귀로 값을 계산한 다음 그 값을 배열에 저장해 뒀다가 다음 번에 사용)

• 자료형 & Overflow에 대한 판단 ..? → 처음에 자료형을 int로 두고 풀었다가 틀렸었다. 질문 검색에서 int자료형에서는 오버플로우가 발생한다는 사실을 깨닫고 long으로 고쳐서 맞았음.
  앞으로는 어림짐작으로라도 2147483647 넘어갈지 정도는 미리 고려해 보자.

---

백준 #1149

RGB 거리

link : https://www.acmicpc.net/problem/1149

#include <iostream>
#include <vector>

using namespace std;

vector<int> res;
vector<int> R;
vector<int> G;
vector<int> B;

int min2(int a, int b) {
    if(a < b) return a;
    else return b;
}

int min3(int a, int b, int c) {
    if(a < b) {
        if (a < c) return a;
        else return c;    // c < a < b
    }
    else {   // b < a
        if (b < c) return b;
        else return c;    // c < b < a
    }
}

void RGBCost(int N) {
    int curR, curG, curB;
    
    cin>>curR>>curG>>curB;
    R.push_back(curR);
    G.push_back(curG);
    B.push_back(curB);
    res.push_back(min3(R[0], G[0], B[0]));
    
    for(int i=1; i<N; i++) {
        cin>>curR>>curG>>curB;
        R.push_back(min2(G[i-1] + curR, B[i-1] + curR));
        G.push_back(min2(R[i-1] + curG, B[i-1] + curG));
        B.push_back(min2(R[i-1] + curB, G[i-1] + curB));
        res.push_back(min3(R[i], G[i], B[i]));
    }
    
}

int main(void) {
    int N;
    
    cin>>N;
    RGBCost(N);
    cout<<res[N-1]<<endl;
    
    return 0;
}

• Bottom-up 방식으로 해결한 문제. 코드를 비교하기 위해 구글링을 하다가 이 문제 & 비슷한 해결 방식이 전형적인 DP 유형이라는 것을 본 것 같기도 하다.

• N번째 집에서 R, G, B 각각의 색상으로 집을 칠할 때 최소 비용을 모두 알아야 한다. (첫 번째 집에서 R이 최소 비용이라 쳐도, 최종 답에서 첫 번째 집을 R로 칠했을 것이라는 보장은 없다.) 즉, Greedy 알고리즘이 통하지 않는 문제이다. (맞나? 사실 그리디 알고리즘이 이게 맞는지 기억이 가물가물 ...)

---

백준 #1932

정수 삼각형

link : https://www.acmicpc.net/problem/1932

#include <iostream>
#include <cstdio>

int intTri[501][501];
int cur[501][501];

int max2(int a, int b) {
    if(a < b) return b;
    else return a;
}

int main(void) {
    int n;
    int res = 0;
    
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            scanf("%d", &intTri[i][j]);
        }
    }
    cur[0][0] = intTri[0][0];
    
    for(int i=1; i<n; i++) {
        for(int j=0 ; j<=i; j++) {
            if (j == 0) cur[i][0] = cur[i-1][0] + intTri[i][0];
            else if (j == i) cur[i][j] = cur[i-1][j-1] + intTri[i][j];
            else {
                cur[i][j] = max2(cur[i-1][j-1], cur[i-1][j]) + intTri[i][j];
            }
        }
    }
    
    for(int i=0; i<n; i++) {
        res = max2(res, cur[n-1][i]);
    }
    
    printf("%d\n", res);
    
    return 0;
}

• 바로 전에 푼 'RGB 거리' 문제와 아주 유사한 문제이다. 둘을 같이 보면 좋을 것 같다.

---

백준 #1463

1로 만들기

link : https://www.acmicpc.net/problem/1463

#include <iostream>

int res[1000001] = {0, };

int min2(int a, int b) {
    if(a < b) return a;
    else return b;
}

int main(void) {
    int N;
    
    res[1] = 0;
    
    std::cin>>N;
    
    for(int i=2; i<=N; i++) {
        if(i % 6 == 0)
            res[i] = min2(res[i-1] + 1, min2(res[i/2] + 1, res[i/3] + 1));
        else if(i % 3 == 0)
            res[i] = min2(res[i-1] + 1, res[i/3] + 1);
        else if(i % 2 == 0)
            res[i] = min2(res[i-1] + 1, res[i/2] + 1);
        else
            res[i] = res[i-1] + 1;
    }
    
    std::cout<<res[N]<<std::endl;
    
    return 0;
}

• 오래 전에 학교에서 알고리즘 과목을 들을 때 굉장히 비슷한 코드를 배웠거나 구현했던 것 같다. 그저 갓도길 ...

• 이 문제를 넣은 이유는, 처음에 Top-down 방식으로 해결하려 했다가, 내 코드에 이상이 있음을 깨닫고 Bottom-up 방식으로 선회해서이다.
  뇌피셜이지만 ,, 설령 Top-down으로 해결할 수 있다 해도 코드가 복잡해질 것 같은 기분이 강하게 든다.

---

끝. 어서 나머지 문제도 풀어서 동적 계획법 1의 마무리를 얼른 블로그에 보고할 수 있도록 하자! 부지런히 살자 ..
<0302 추가> 결국 이번 방학 때 알고리즘 공부는 내팽개쳐두고, 웹 개발 공부에만 치중했다. 이번 학기는 휴학도 했겠다, 셀프 개강 느낌으로 1일 1백준을 실천하도록 하자.