/ BOJ

BOJ_9095_123더하기_JAVA

문제 : 123더하기

링크 : BOJ_9095_123더하기

접근 방식

1,2,3을 각각 더해서 특정 수를 만들어내야 하는 문제이다. 3을 예로 들어보겠다.

1 + 1 + 1 1 + 2 2 + 1 3

이렇게 총 4 가지 경우의 수가 있다.

보면 알 수 있듯이, 중복되더라도 순서가 다르면 다른 경우로 친다.

나는 DFS를 통해 문제를 풀었다.

풀이 방법

  1. 주어진 값을 읽어와 N에 저장하고 dfs를 돌린다. 인자값으로는 현재 선택한 숫자(1,2,3)변수 x 와 값을 더해서 누적시킬 변수 val으로 받는다.

  2. 기저조건으로는 val이 N에 도달하면 멈추도록한다. 이때 카운트를 1 증가시킨다.

  3. 1,2,3 각각 선택하는 경우가 있으므로 반복 재귀를 통해 각각의 수를 넘겨준다. 대신, 현재 N보다 작을 경우에만 재귀호출한다. N값을 넘어선 경우 멈춰야 하기 때문이다.

  4. dfs가 종료되고 카운트 값을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_9095_123더하기 {

	static int cnt, N;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for(int tc=0;tc<T;tc++) {

			N = Integer.parseInt(in.readLine());
			cnt = 0;
			dfs(1,0);

			System.out.println(cnt);

		}
	}

	public static void dfs(int x, int val) {
		// 기저조건
		if(val == N) {
			cnt++;
			return;
		}

		for(int i=1;i<=3;i++) {
			if(val < N) {
				dfs(i, val+i);
			}
		}

	}
}