이독 과제로 푼 두 문제

그녀를 찾아서

DP보다는 확통 문제 아닌가…? 라는 생각이 가장 먼저 들었다

이렇게 생각해볼 수 있을 것 같음

먼저 초기에 각 노드로 들어가는 확률은 모두 동일하니까 그 값으로 정해준 다음 10분 간격으로 한 칸씩 옮겨주면 되는 거임. 근데 그 때 계산을 위해서 주어진 확률을 사용하는 것.

문제에서 주어진 예를 가지고 생각해보자. 이 경우는 정점은 모두 4개니 초기 확률은 0.25가 된다. (추가 : 문제 제대로 안 읽었다 항상 정점은 4개다; 제발) 그리고 모든 정점에 대해서 확률을 계산해보자.

계산한 노드ABCD
A00.2500
B00.250.0750.175
C0.150.250.0750.175+0.1
D0.150.250.0750.175+0.1+0.25
다음과 같이 구할 수 있을 것이다.

이 때 초기 확률을 모두 합한 값이 1인데, 한 정점에서 다른 정점으로 갈라지는 확률의 합도 1이므로 (x + y + z + …) x 1 = 1이 된다. 퍼센티지로 리턴하라고 했으니 100을 곱해주면 되고, 상대오차가 $10^{-2}$까지 허락되므로 소수점을 둘째자리까지 표시해주면 안전할 것이다.

그럼 코드를 짜볼까요?

//그녀를 찾아서 - 실버 3  
#include <bits/stdc++.h>  
  
using namespace std;  
  
typedef pair<int, double> pid;  
  
int t, m;  
  
vector<vector<pid>> graph;  
  
int main() {  
    cin >> t >> m;  
    graph.assign(4, vector<pid>());  
  
    for (int i = 0; i < m; i++) {  
        char a, b;  
        double c;  
        cin >> a >> b >> c;  
        graph[a-'A'].push_back({b-'A', c});  
    }  
  
    vector<vector<double>> dp(t+1, vector<double> (4, 0));  
  
  
    for (int i = 0; i < 4; i++) {  
        dp[0][i] = (double)1 / 4;  
    }  
  
    // 시간 : 1에서부터 t일 때까지 반복  
    for (int i = 1; i <= t; i++) {  
        for (int j = 0; j < 4; j++) {  
            int cur = j;  
            for (auto next : graph[cur]) {  
                dp[i][next.first] += dp[i-1][cur] * next.second;  
            }  
        }  
    }  
  
    cout << setprecision(2) << fixed;  
    for (int i = 0; i < 4; i++) {  
        cout << dp[t][i] * 100 << '\n';  
    }  
}

무난하게 맞음 👍 cout << setprecision() << fixed 이거 진짜 좀 외워야겠음;

좁은 미술전시관

보자마자 생각난 문제는 이거 근데 이 문제는 떼야 하는 스티커의 개수가 정해져 있지 않아서 이 문제가 조금 더 까다롭다고 할 수 있음ㅇㅇ 골드 5면 딱 적당한 듯

일단 든 생각은 탐다운으로 구현하는 편이 훨씬 편할 것 같다는 거… 완전탐색할 때 재귀로 빠져나오는 횟수 카운트 해주는 것처럼 얘도 그렇게 해서 닫아야 하는 방 개수가 찼을 때 나오게 하는 게 좋지 않을까 생각함

진짜 최악 케이스를 가정하면 n이 200이고 k가 100, 그리고 매 칸이 다 떨어져있어서 왼쪽 오른쪽이 100퍼 랜덤인 케이스를 생각해볼 수가 있을 것 같은데 이럼 200C100 * 2^100이니까… 2의 100승이 10만 정도 되고 앞이 200!/(100! * 100!)이 되는 건데 보나마나 20억이 넘어갈 것이 뻔하기 때문에… 저장하면서 값을 구하는 수 밖에 없다

까지 생각하고 더 이상 생각이 진전이 안 돼서 결국 구글링했다; 당장 배열부터 어떻게 짜는지 떠오르지가 않았는데 다음 블로그의 글을 보고 무릎을 탁! 쳤다…

링크

내가 고민했던 지점을 나누어서 설명해보자면

  1. 현재 상태를 저장해야 하는데, 이걸 어떻게 저장하지? 그러니까 지금 한 줄에 방이 왼쪽만 닫히거나, 오른쪽만 닫히거나, 아님 아예 안 닫히거나 이걸 표현을 해야 하는데 어떻게 하지…?
    • A : 그냥 상태를 3개 만들면 되는 일이었음. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
    • 해당 줄에 모든 문이 열려있는 것도 분명히 존재하는 케이스니까,,, 그리고 다음 칸에서 고려할 때도 전 줄에서 모든 문이 열려있는 케이스인지가 충분히 고려사항이 되기 때문에…
    • 이거랑 비슷한 문제로 스티커 문제가 있는데 여기서는 배열을 만들 때 상태를 애초에 무조건 붙인다!로 만들어서 그거 때문에 아무 문도 닫지 않는다!라는 선택지가 존재할 수 없을 거라고 생각했던 것 같음… 근데 저 문제는 붙이는 개수의 제한이 없어서 붙일 수 있다면 최대한 붙이는 편이 이득인 문제라서 그렇게 상태를 위 아래 두 개로 해도 문제가 없었던 거고 이 문제는 개수 제한이 있다는 게 차이점임… 근데 스티커도 지금 다른 사람들 푼 거 보니까 상태 3개로 해서 푼 사람들도 있네 머쓱;
  2. 방 개수가 제한되어 있는데 이걸 배열에 어떻게 저장하지?
    • A : 그냥 방 개수도 상태를 만들면 되는 일이었음…
    • 이걸 명심해야 될 것 같음
    • dp 배열에는 해당 문제에서 가능한 모든 상태를 저장한다!!!
    • 그니까 방 개수도 엄연한 상태 중 하나기 때문에 이걸 저장하는 칼럼을 하나 더 만들어서 관리하면 그만이다 이 말임…

이렇게 해서 일단 배열로 상태를 어떻게 표현할 지를 생각해두면 점화식을 세울 수 있고? 점화식을 세우면 탑다운이든 바텀업이든 모든 상태를 계산하는 연산을 어떻게 수행할 지를 떠올릴 수 있음…

점화식을 세워보자면 다음과 같음. 상태는 0이 왼쪽 닫힘, 1이 오른쪽 닫힘, 2가 다 열림임 그리고 배열이 나타내는 것은 해당 상태일 때 가치의 최댓값.

$$ dp[line][closed_cnt][state] $$ $$ dp[line][closed_cnt][0] = max(dp[line-1][closed_cnt-1][0], dp[line-1][closed_cnt-1][2] + board[line][1]) $$ $$ dp[line][closed_cnt][1] = max(dp[line-1][closed_cnt-1][1], dp[line-1][closed_cnt][2])+board[line][0] $$ $$ dp[line][closed_cnt][2] = max(dp[line-1][closed_cnt-1][0], dp[line-1][closed_cnt][1], dp[line-1][closed_cnt][2])+board[line][0]+board[line][1] $$ 이 점화식을 바탕으로 코드를 짜 보겠음.

//좁은 미술전시관 - 골드 5  
#include <bits/stdc++.h>  
  
using namespace std;  
  
int n, k;  
  
vector<vector<int>> board;  
vector<vector<vector<int>>> dp;  
  
int main() {  
    cin >> n >> k;  
    board.assign(n+1, vector<int> (2, 0));  
    dp.assign(n+1, vector<vector<int>> (k+1, vector<int> (3, 0)));  
  
    for (int i = 1; i <= n; i++) {  
        cin >> board[i][0] >> board[i][1];  
    }  
    //0 : 왼쪽 닫, 1 : 오른쪽 닫, 2 : 다 열림  
    dp[1][1][0] = board[1][1];  
    dp[1][1][1] = board[1][0];  
    dp[1][0][2] = board[1][0] + board[1][1];  
  
    for (int j = 0; j <= k; j++) {  
        for (int i = 2; i <= n; i++) {  
            if (j) {  
                dp[i][j][0] = max(dp[i-1][j-1][0], dp[i-1][j-1][2]) + board[i][0];  
                dp[i][j][1] = max(dp[i-1][j-1][1], dp[i-1][j-1][2]) + board[i][1];  
            }  
            dp[i][j][2] = max({dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2]}) + board[i][0] + board[i][1];  
        }  
    }  
  
    cout << max({dp[n][k][0], dp[n][k][1], dp[n][k][2]});  
}

일단 이렇게 짬 그리고 WA!

//좁은 미술전시관 - 골드 5  
#include <bits/stdc++.h>  
  
using namespace std;  
  
int n, k;  
  
vector<vector<int>> board;  
vector<vector<vector<int>>> dp;  
  
int main() {  
    cin >> n >> k;  
    board.assign(n+1, vector<int> (2, 0));  
    dp.assign(n+2, vector<vector<int>> (k+2, vector<int> (3, 0)));  
  
    for (int i = 1; i <= n; i++) {  
        cin >> board[i][0] >> board[i][1];  
    }  
    //0 : 왼쪽 닫, 1 : 오른쪽 닫, 2 : 다 열림  
    dp[1][1][0] = board[1][1];  
    dp[1][1][1] = board[1][0];  
    dp[1][0][2] = board[1][0] + board[1][1];  
  
    for (int j = 0; j <= k; j++) {  
        for (int i = 2; i <= n; i++) {  
            //닫은 문의 개수가 라인보다 클 때 -> skip            
            if (j > i) continue;  
            if (j) {  
                dp[i][j][0] = max(dp[i-1][j-1][0], dp[i-1][j-1][2]) + board[i][1];  
                dp[i][j][1] = max(dp[i-1][j-1][1], dp[i-1][j-1][2]) + board[i][0];  
            }  
            if (i != j)  
                dp[i][j][2] = max({dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2]}) + board[i][0] + board[i][1];  
        }  
    }  
  
    cout << max({dp[n][k][0], dp[n][k][1], dp[n][k][2]});  
}

이렇게 고쳐봄. 그러고 맞음.

근데 왜 맞는지 모르겠음ㅋㅋㅋㅋㅋ

일단 저 $i\ne j$ 저거 넣으니까 왜 맞지….??????? 참고한 블로그에서 넣은 코드라 똑같이 넣어봤는데 맞음 그리고 이해를 위해서 닫은 문 개수보다 라인이 작으면 continue하게 만들었는데 뭔가 디버깅한 작동이 내가 생각한 거랑 다름,,,,,, 뭐지…? 마지막으로 outofbounds 떠서 dp 배열 인덱스를 한 칸씩 늘려줬는데 갑자기 에러 안 뜸…? 왜????

좀 더 생각해봐야겠음 맞긴 맞았는데…. 아무튼 맞긴 함!