[알고리즘 문제 풀기] 스티커(9465)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int t = int.Parse(sr.ReadLine());
    while (t > 0)
    {
        t--;
        int n = int.Parse(sr.ReadLine());
        int[][] s = new int[2][];
        s[0] = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        s[1] = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        int[,] dp = new int[2, n + 1];
        dp[0, 1] = s[0][0];
        dp[1, 1] = s[1][0];
        for (int i = 2; i <= n; i++)
        {
            dp[0, i] = s[0][i - 1] + Math.Max(dp[1, i - 2], dp[1, i - 1]);
            dp[1, i] = s[1][i - 1] + Math.Max(dp[0, i - 2], dp[0, i - 1]);
        }
        sb.AppendLine(Math.Max(dp[0, n], dp[1, n]).ToString());
    }
    sw.Write(sb);
}

3. 정리

• s[0][i], s[1][i]는 i번째 열의 위쪽과 아래쪽 스티커의 점수를 저장한다.

• dp[0][i]는 i번째 열에서 위쪽 스티커를 선택했을 때 얻을 수 있는 최대 점수를 저장한다.

• dp[1][i]는 i번째 열에서 아래쪽 스티커를 선택했을 때 얻을 수 있는 최대 점수를 저장한다.

• dp[0][i]는 s[0][i-1]에 dp[1][i-1] 또는 dp[1][i-2] 중 큰 값을 더하여 갱신한다.

• dp[1][i]는 s[1][i-1]에 dp[0][i-1] 또는 dp[0][i-2] 중 큰 값을 더하여 갱신한다.

• 최종적으로 dp[0][n]과 dp[1][n] 중 최댓값을 출력한다.