문제 탐색하기
입력 자료 정리
- 첫번째 입력값은 이후 들어올 입력값의 수인 테스트케이스 수이다
- 이후 들어오는 테스트케이스 수만큼의 입력값들은
몇번째 인덱스에 있는 dp 배열의 값을 출력할지에 대한 값이다
해결방법 추론
- 이 문제의 풀이는 두가지를 생각할 수 있다.
가장 쉬운 첫번째 방법은 4를 나타내는 방법은 7가지가 있다는 문제를 보고,
1, 2, 3일때는 어떤 경우의 수를 가지며 규칙이 무엇이 있을까 고민해서 나온 규칙으로 푸는
DP 방법이 있을 것이다 - 이어서 두번째 방법은 최대 n이 11보다 작다는 점과,
선택할 수 있는 숫자도 1,2,3으로 3가지라는 점을 이용하여 백트래킹으로 푸는 방법이다
놀랍게도 백트래킹으로 풀어도 시간제한이나 메모리제한 없이 문제가 해결된다 - 두가지 방법 모두로 풀어보았다. 먼저 DP로 푼 방법부터 설명하겠다
점화식 추론
- 점화식을 추론해낸 과정은 다음과 같다.
4를 1,2,3으로 나타내는 방법이 7가지 있으니까 1,2,3 각각을 나타내는 방법은 몇가지 있을까
고민하고 찾아봤다 - 1,2,3은 각각 1, 2, 4가지 경우가 있었다. 이때 이 3가지를 더하면 4를 나타내는 방법이 된다
- 그렇다면 점화식은 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]이 되겠는데,
과연 이 점화식이 맞을까라는 의문을 품었다 - 5와 6으로 검증을 하기 위해서는 내가 직접 경우의 수를 구해야한다.
하지만 경우의 수를 구하는 것에서 오류가 발생할 수 있고, 따라서 예제 입력에서 주어진
7을 통해 검증하기로 하였다 - 위 점화식에 의하면 5와 6은 간단히 구할 수 있다.
5는 2 + 4 + 7으로 13이 되며, 6은 4 + 7 + 13으로 24가 된다 - 그렇다면 7은 어떻게 될까? 7 + 13 + 24가 되며, 합하면 44가 된다.
예제 출력의 결과와 일치한다. - 따라서 점화식은 위에 나온 식이 맞으며 해당 방법으로 문제를 풀면 해결 될 것이다
DP 풀이 시간복잡도 계산
- 테스트케이스는 최대 입력값을 주지 않았기 때문에 시간복잡도에서 제외하면,
최대 입력값인 10이 최대 연산이 될 것이다. - 그리고 이것은 배열에 넣는 과정에서만 발생하므로 시간복잡도는 상수 시간이 발생한다
- 따라서 DP 풀이에서의 시간복잡도는 O(1)이 되며, 시간 제한안에 문제를 해결할 수 있다
백트래킹 해결방법 고민
- 백트래킹으로도 문제를 해결할 수 있다. n의 입력값이 매우 작기때문에 가능하다
- 진행해온 경로를 백트래킹 파라미터로 누적해서 관리하며,
합산으로 base condition역할을 한다면 쉽게 구할 수 있을 것이다 - 이때 선택한 경로가 중복되는 경우를 제외하기 위해 Set 자료구조를 사용한다면
더 편하게 문제를 해결할 수 있다
백트래킹 풀이 시간복잡도 계산
- 백트래킹 풀이의 시간복잡도는 테스트케이스마다 백트래킹을 실행하므로
테스트케이스만큼의 시간복잡도가 발생함을 고려하기는 해야한다 - 하지만 테스트케이스의 최대 입력값이 안 주어졌기 때문에
문제를 해결할 수 있을 만큼의 테스트케이스를 줄 것이므로 크게 고려하지 않아도 된다 - 백트래킹의 시간복잡도만 생각하면 된다. 매 함수실행마다 3가지 경우를 선택한다
- 이때, 최악의 경우 1만 선택되어서 n번만큼 실행되는 경우이므로 3^n만큼의 연산이 발생할 것이다
- 따라서 시간복잡도는 O(3^n)일 것이고 최대 입력값 10을 생각했을 때,
시간제한안에 문제를 해결할 수 있다
코드 설계하기
DP값 상태 관리하기
- DP의 값은 미리 1번 인덱스부터 10번 인덱스까지 구해서 int형 1차원 배열로 관리한다
- 이때 1,2,3은 미리 1,2,4로 초기화하고 4번 인덱스부터는 점화식으로 값을 구해 관리한다
테스트케이스 출력 설계
- 테스트케이스는 T라는 이름의 int형 변수로 관리한다
- 이후 들어오는 입력값은 dp의 인덱스 값이며, 이 인덱스에 해당되는 값을 출력하면 정답이 된다
backtracking 설계
- 1,2,3 선택을 편하게 하기 위한 int형 1차원 배열을 하나 선언하고 원소값으로 1,2,3을 관리한다
- 또한 중복 제거를 위한 Set을 하나 만든다.
String 타입으로 선택 경로를 관리하며, 매 입력마다 Set을 초기화하여 이전 결과의 영향을 받지 않도록 한다 - 백트래킹의 base condition은 sum이 n보다 크거나 같은 경우이며,
이때 n과 같은 경우 set에다가 진행 경로인 String 값을 추가한다 - select 배열의 크기인 3만큼 순회하면서 재귀식을 실행하고,
선택된 값의 원소를 sum에 더하며, 문자열로 파싱해서 경로에다가 추가한다
backtracking 결과 출력
- 완성된 Set의 크기를 출력하면 정답이 된다
정답 코드
(dp 풀이, 1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
int[] dp = new int[11];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i < 11; i++) {
dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
}
for (int i = 0; i < T; i++) {
int n = Integer.parseInt(br.readLine());
bw.write(dp[n]+"\n");
}
br.close();
bw.close();
}
}(백트래킹 풀이, 1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
static int[] select = {1,2,3};
static Set<String> set;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int n = Integer.parseInt(br.readLine());
set = new HashSet<>();
backtracking(n,0,"");
bw.write(set.size()+"\n");
}
br.close();
bw.close();
}
private static void backtracking(int n, int sum, String ans) {
if(sum >= n){
if(sum == n){
set.add(ans);
}
return;
}
for (int i = 0; i < 3; i++) {
backtracking(n,sum+select[i], ans + String.valueOf(select[i]));
}
}
}문제 링크
Software Developer