[TIL] 24.02.29

1. 알고리즘 문제 해결

 

쉬운 계단 수(백준 10844):

 간단한 DP문제, 주어진 N이 워낙 작아서 끝자리 숫자 기준으로 2차원 DP 테이블을 생성해 모두 탐색해주면 된다.

오히려 오버플로우 때문에 모듈러 연산 적용하는 것에 더 신경써야 하는 문제.

 

 

 

동물원(백준 1309):

 위의 계단 수 문제와 유사한 문제. 좌우칸을 나누어 생각할 필요 없이, 사자가 해당 행에 위치하는지 아닌지만 따지면 된다. 어차피 가로로도, 세로로도 사자가 붙어있게 배치될 수 없기 때문에, 사자가 한 행에 배치되면 다음 행에 배치될 수 있는 사자의 위치는 고정된다.

 따라서 앞의 행에 사자가 없는 경우에는 사자가 배치되는 경우가 2가지 생길 수 있고, 앞의 행에 사자가 있는 경우에는 배치되는 경우가 1가지가 생기게 된다. 그리고 첫 행에, 사자가 없는 경우 1가지, 사자가 있는 경우 2가지(왼쪽, 오른쪽)로 둘 수 있으므로, 이에 대해 점화식을 적용한 DP를 구현하면 쉽게 해결할 수 있다.

 

 

내려가기(백준 2096):

 이것도 DP문제이다. 그런데 무턱대고 N*3크기의 DP 테이블을 생성했다간, 최대 100,000*3*2(min과 max)*4Bytes 로 대략 2.4MB 정도의 메모리를 차지하게 되는데 꽤나 빡빡하다. 만약 인풋값도 모두 2차원 배열에 저장한다면 훨씬 더 타이트해지기 때문에 이는 적절한 접근은 아니다.

 하지만 조금만 생각해보면, 이 문제 또한 DP를 적용할 때 필요한 것은 별표의 위치별 직전 최대, 최소값들 뿐이다. 해당 값들만 있다면 문제 조건에 맞추어 내려가기를 한 결과를 구해낼 수 있다. 따라서 입력을 받으며 한 줄씩 DP로 처리해주고, 마지막에 얻어진 위치별 최대, 최소값들을 최종적으로 비교한 최대, 최소값을 구해 출력하면 해결된다.

 

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

    int n;

    cin >> n;

    vector<pair<int, int> > dp(3, {0, 0}); //{min, max}

    for(int play=0; play<n; play++) {

        int left, mid, right;

        pair<int, int> leftP, midP, rightP;

        cin >> left >> mid >> right;

        leftP.first = min(dp[0].first+left, dp[1].first+left);

        leftP.second = max(dp[0].second+left, dp[1].second+left);

        midP.first = min(dp[0].first+mid, min(dp[1].first+mid, dp[2].first+mid));

        midP.second = max(dp[0].second+mid, max(dp[1].second+mid, dp[2].second+mid));

        rightP.first = min(dp[1].first+right, dp[2].first+right);

        rightP.second = max(dp[1].second+right, dp[2].second+right);

        dp[0] = leftP;

        dp[1] = midP;

        dp[2] = rightP;

    }

    cout << max(dp[0].second, max(dp[1].second, dp[2].second)) << " " << min(dp[0].first, min(dp[1].first, dp[2].first));

}