[백준 / BOJ] 14650 걷다보니 신천역 삼 (small)

문제

출처 : www.acmicpc.net/problem/14650

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

N을 입력받았을때,

0 , 1 , 2만을 가지고 N자리 3의 배수를 만들어야한다.

 

N = 1 이라면

0 , 1 , 2 로 만들수있는 3의 배수가 없으니 0 출력

 

N = 2 라면

1 2

2 1 두가지를 만들수있다.

(현재 숫자에 더하는게 아니라 숫자를 이어붙이는 형식임에 주의하자)

풀이

완전 탐색 문제다.

 

3의 배수가 갖는 규칙을 찾는게 중요했는데,

3의 배수라면, (각 자리 수를 모두 더한값 % 3 == 0) 이다. 

 

예를들어, N = 2라면

1 2

2 1

이렇게 두가지가 나오는데 두 수 모두 3의 배수가 나온다.

 

또, N = 3 이라면,

1 2 0

1 0 2

2 1 0

.

.

.

총 6개가 나오는데, 각 자리를 모두 더한값은 3의 배수이다.

 

만들숫자가 1로 시작했을때와 2로 시작했을때 두가지 경우로 완전탐색을 돌려주면서 3의 배수라면 종료한다. 

1로 시작했을때와 2로시작했을때로 두번 돌리는 이유는, 맨 앞자리 숫자가 1 일때와 2일때를 봐줘야하기 때문이다. (0은 맨 앞자리로 올수가없다.)

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14650%20%EA%B1%B7%EB%8B%A4%EB%B3%B4%EB%8B%88%20%EC%8B%A0%EC%B2%9C%EC%97%AD%20%EC%82%BC%20(small)/main.cpp

devxb/JJUNalgo