문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 14652번 나는 행복합니다~ (0) | 2018.08.07 |
---|---|
백준 14651번 걷다보니 신천역 삼(Large) (0) | 2018.08.07 |
백준 1194번 달이 차오른다, 가자 (6) | 2018.08.05 |
백준 10775번 공항 (2) | 2018.08.05 |
백준 4195번 친구 네트워크 (11) | 2018.08.05 |