백준 14650번 걷다보니 신천역 삼(Small)

문제 링크입니다: https://www.acmicpc.net/problem/14650

N의 범위가 작기 때문에 해당 문제는 브루트 포스(Brute Force) 방식으로 풀어도 되는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 각 자리 수에 숫자를 추가합니다.

2. 마지막 자리 수에 숫자를 추가했을 때 조건을 살핍니다.

i) 각 자리 수의 합이 3으로 나누어 떨어지면 3의 배수

ii) 이외의 경우는 3의 배수가 아닙니다.

#include <iostream>

using namespace std;

 

int N;

 

long long multipleOfThree(int num, int sum, int length)

{

        //조건 충족

        if (length == 1 && sum % 3 == 0)

                 return 1;

        //조건 불충족

        else if (length == 1)

                 return 0;

 

        long long result = 0;

        for (int i = 0; i <= 2; i++)

                 result += multipleOfThree(i, sum + i, length - 1);

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

 

        if (N == 1)

                 cout << 0 << "\n";

        else

        {

                 long long result = 0;

                 //0으로 시작할 수 없다

                 for (int i = 1; i <= 2; i++)

                         result += multipleOfThree(i, i, N);

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~