[백준 9095번] 1, 2, 3 더하기 (자바)

백준알고리즘 9095번 : 1, 2, 3 더하기 (Solved.ac 난이도 Silver3)

 

↑클릭시 문제 link로 이동합니다.😊

 

 

DP(Dynamic Programming), 동적 프로그래밍의 기본 문제이다.

동적 프로그래밍을 풀이하는데에는 Bottom-up 방식과 Top-down 방식이있다.

이 문제는 Bottom-up 방식으로 풀어보았다.

문제를 작은 단위의 문제로 쪼개서 풀어야하는 만큼,
최소 단위 정도는 내가 직접 풀어보아야한다.

이 문제는 1,2,3의 숫자만 이용하여 만들수 있는 집합의 개수를 구하는 문제이다.

4부터는 '1+ [3으로 만들 수 있는 집합의 개수] / 2 + [2로 만들 수 있는 집합의 개수] /

           3 + [1으로 만들 수 있는 집합의 개수]'로 쪼갤 수 있기때문에, 3까지만 내가 풀어보았다.

1로 만들수 있는 집합의 개수 : 1개 {1}
2로 만들수 있는 집합의 개수 : 2개 {1,1}, {2}
3으로 만들수 있는 집합의 개수 : 4개 {1,1,1}, {1,2}, {2,1}, {3}

따라서 4로 만들 수 있는 집합의 개수는 7개가 된다.
Case 1 : 숫자 1이 앞에 나오는 경우 (=3으로 만들 수 있는 집합의 개수) = 4개
Case 2 : 숫자 2가 앞에 나오는 경우 (=2로 만들 수 있는 집합의 개수) = 2개
Case 3 : 숫자 3이 앞에 나오는 경우 (=1으로 만들 수 있는 집합의 개수) = 1개
Case 1+2+3 = 7

이제 이것을 알고리즘으로 구현해주면 된다.

 

 

풀이 과정

---

1. 테스트케이스마다 숫자의 합을 새로 구해줄 필요는 없으므로 TestCase에서 발생할 수 있는 최대 크기의 정수만큼 배열을 생성하고, 배열의 1, 2, 3번째에 내가 구한 값을 넣는다.
2. for문을 한차례 돌면서 최대 크기의 정수까지 답을 구한다.
3. TestCase를 돌려 해당하는 값을 배열에서 찾아 출력한다. 

 

▽ 정답 소스 보기

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

public class Main {// No9095_Bottom-up : 1, 2, 3 더하기

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		int[] method = new int[11];
		method[1] = 1;
		method[2] = 2;
		method[3] = 4;

		for (int i = 4; i < method.length; i++) {
			method[i] = method[i - 1] + method[i - 2] + method[i - 3];
		}
		for (int i = 0; i < testCase; i++) {
			int ask = Integer.parseInt(br.readLine());
			System.out.println(method[ask]);
		}

	}
}

 

 

 

+ 다음으로는 Top-down 방식으로 구현한 경우이다.

재귀 함수를 사용하여 이미 값이 있다면 바로 return하여 계산의 중복을 피해주었다.
시간차이는 얼마 나지 않는다. 다른 문제에서 다시 양방향으로 풀어보아야겠다.

 

▽ 정답 소스 보기

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

public class Main {// No9095_Top-down : 1, 2, 3 더하기
	static int[] method = new int [11];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		method[1] = 1;
		method[2] = 2;
		method[3] = 4;

		for (int i = 0; i < testCase; i++) {
			int ask = Integer.parseInt(br.readLine());
			System.out.println(dp(ask));
		}

	}
	public static int dp(int a) {
		if (method[a]!=0) {
			return method[a];
		}else {
			method[a]=dp(a-1)+dp(a-2)+dp(a-3);
			return method[a];
		}
	}
}