[C++] 백준 8394번 악수

https://www.acmicpc.net/problem/8394

풀이

dp(i): i번째 사람까지 악수하는 경우의 수
라고 정의할 때, 앞 사람과 악수하는지 여부로 경우를 나눌 수 있다.

dp(i) = dp(i, 0) + dp(i, 1)

• dp(i, 0): i번째 사람이 i-1번째 사람과 악수하지 않음
• dp(i, 1): i번째 사람이 i-1번째 사람과 악수함

이때, 아래와 같이 점화식을 정의할 수 있다.

• dp(i, 0) = dp(i-1, 0) + dp(i-1, 1)
  : i-1번째 사람은 i-2번째 사람과 악수할 수도, 하지 않을 수도 있음
• dp(i, 1) = dp(i-1, 0)
  : i-1번째 사람은 i-2번째 사람과 악수하지 않음

그리고 i = 1일 때, 경우의 수는 다음과 같다.
dp(1, 0) = 1
dp(1, 1) = 0

오답 코드 - 메모리 초과

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<vector<int>> dp(n+1, vector<int>(2,0));
    dp[1][0] = 1;
    dp[1][1] = 0;
    for(int i=2; i<=n; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }
    
    cout << dp[n][0] + dp[n][1];

    return 0;
}

• n이 최대 10,000,000이므로 2차원 vector 사용 시 메모리 초과가 발생하였다.
• 또한, "마지막 자리만 출력한다." 라는 조건도 만족하지 않았다.

정답 코드

#include <iostream>
using namespace std;

int dp[10000001][2];

int main()
{
    int n;
    cin >> n;
    
    dp[1][0] = 1;
    for(int i=2; i<=n; i++){
        dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % 10;
        dp[i][1] = dp[i-1][0];
    }
    
    cout << (dp[n][0] + dp[n][1]) % 10;

    return 0;
}

• 2차원 배열을 사용하여 메모리 초과를 방지하였다.
• + 연산시 일의 자리 수만 저장하도록 코드를 변경하였다.