[알고리즘 문제 풀기] 걷다보니 신천역 삼 (Small)(14650)

1. 문제 풀이 아이디어

• DFS를 이용해 모든 경우를 탐색하며, 자리수가 n이 되었을 때 합이 3의 배수이면 결과를 증가시킨다.

2. 나의 정답 코드

using (StreamReader sr = new(Console.OpenStandardInput()))
using (StreamWriter sw = new(Console.OpenStandardOutput()))
{
    
    int n = int.Parse(sr.ReadLine());
    int result = 0;
    int count = 0;
    int sum = 0;
    for(int i = 1; i < 3; i++)
    {
        count++;
        sum+=i;
        solve();
        sum -= i;
        count--;
    }
    sw.WriteLine(result);

    void solve()
    {
        if (count == n)
        {
            if (sum != 0 && sum % 3 == 0)
            {
                result++;
            }
            return;
        }
        for(int i = 0; i < 3; i++)
        {
            count++;
            sum += i;
            solve();
            sum -= i;
            count--;
        }
    }
}

3. 정리

• 첫 자리 숫자는 1과 2만 허용하며, 이후에는 0, 1, 2를 모두 고려한다.

• count == n일 때 합이 3의 배수이면 결과를 증가시킨다.

• 백트래킹을 이용해 sum과 count 값을 원래 상태로 복구하며 탐색을 진행한다.