[백준 - JAVA] 걷다보니 신천역 삼 (Small)

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

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

http://boj.kr/98072675427b44138b7510ebc433fe2a

공유 소스 보기

import java.util.Scanner;

class Main{
    
    public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int inputNumber = sc.nextInt(),
			result = 0, pardon;
		
		int[] arr = new int[inputNumber];
		
		arr[0] = 1;
		
		while(arr[0] != 3) {
			
			pardon = arr[0];
			
			arr[arr.length - 1]++;
			
			for(int i = arr.length - 1; i > 0; i--) {
				
				if(arr[i] == 3) {
					
					arr[i - 1]++;
					arr[i] = 0;
					pardon += arr[i];
					
				}else {
					
					pardon += arr[i];
					
				}
				
			}
			
			if(pardon % 3 == 0) result++;
			
		}
		
		System.out.println(result);

	}
    
}

 

3의 배수는 수를 하나씩 쪼갰을 때,

 

모두 합한 값이 3의 배수이면 된다.

 

n자리 3의 배수 개수를 구하는 거니,

 

각 항을 0, 1, 2가 들어가는 모든 경우의 수를 체크하면 된다.

(첫자리는 0이 못 온다)

 

그래서 3진수 구현해서 모든 경우를 판단하여

 

답을 구했다.