정올 Q1407 숫자카드
최근 연속해서 다이나믹 문제를 풀고 있다. 다이나믹 문제를 풀며 가장 중요한것은 어떤것을 기준으로 잡아 배열을 만들고 어떤방식으로 재활용하느냐 그것이 중요한 부분인것 같다. 문제를 풀며 다양한 형태의 다이나믹 문제 접근방식을 익혀가야겠다.
▶ 문제 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=683&sca=3050
입력 받은 숫자열을 기반으로 숫자를 만들어 가능한 가짓수를 구하여라 1~34를 범위로 한다.
위그림과 같이 27123의 숫자가 주어졌을시 다음과 같이 6가지의 경우의 수를 완성할 수 있다.
71의 경우 34보다 큰 수이므로 불가능하다.
▶ 문제 접근 방법(코딩 이전에 생각한 문제 접근방법)
다이나믹형태로 문제에 접근하는 것을 기본으로 하여 생각해 보자. f(N)의 N을 무엇으로 설정할것인가 우선이 되어야한다. 2개의 숫자로 이루어진 카드의 갯수를 N으로 두고 문제에 접근해보겠다.
예를 들어 f(0)은 모두 1자리 숫자로 이루어진 숫자고 가짓수는 0이된다. 이러한 방식으로 접근해 보겠다. f(N)과 f(N-1....)간의 관계를 찾는 것이 우선되어야 할것이다.
▶ 문제 풀이
예상한 접근 방식엔 문제가 있었다. 기준이 애매했고 f(n)간의 점화식을 찾기에 힘들었다. 이 문제는 점화식문제에 가까웠다. 기본 알고리즘이후에 코드에 대한 설명을 하겠다.
f(N)을 먼저 구하는 것이 문제풀이의 시작으로 하였다. 여기서 N은 카드의 갯수이고 f(N)은 가능한 경우의 수이다.
즉 f(1)은 1가지 카드로 조합가능한 가짓수를 뜻한다. 1가지만 가능하므로 1이다.
f(2)의 경우 1,2/12 2가지 방법이 가능하므로 2이다. f(3)은 3, f(4)는 5, f(5)는 8임을 알 수있다.
즉 f(N )=f(N-1)+f(N-2)의 식이 성립된다. 위 식이 나온것에 대해 설명해 보겠다.
예를 들어 f(4)은 1,2,3,4으로 이루어졌다고 가정하자.
(1~34의 조건은 나중에 생각하고 일단 경우의 수 부터 살펴 보자)
f(3)은 (1,2,3) / (12,3) / (1,23) 이고
f(4)는 (1,2,3,4), (1,2,34) / (12,3,4),(12, 34 ) / (1,23,4) 5가지가 가능하다.
123에 4를 넣는다고 생각해 보자.
(1,2,3),(12,3)과 같이 마지막 숫자가 1개로 이루어진경우 경우의 수가 2배가 되는것을 볼수 있다. ex (1,2,3,4 ),(1,2,34) / (12,3),(12,3,4)
마지막 숫자가 1개로 이루어진 경우의 수는 n-2단계에서 올라온것이므로 f(n-2)와 같다는것을 알수 있다.
즉 f(n-2)*2가 된다.
(1,23)과 같이 마지막 숫자가 2개로 이루어진 경우 갯수가 그대로 올라오는 것을 알수있다. 이것의 갯수는 n-1단계의 총갯수중 마지막숫자열이 2개로 이주어진 경우의수(n-2)를 뺀것이란 것을 알 수 있다.
즉 f(n-1)-f(n-2)가 된다.
따라서 f(n) = f(n-1)-f(n-2)+f(n-2)*2가 되고
다시 정리하면 f(n)=f(n-1)+f(n-2)라는 것을 알 수있다.
주어진 숫자에서 카드패로 만들수 없는 숫자가 나왔을시 자르고 각각의 경우의 수를 곱하는 방식으로 연산하였다.
즉 27123의 경우
27 / 123 으로 나누고 2,7로 만들 수 있는 가짓수 f(2)=2
1,2,3으로 만들 수 있는 가짓수 f(3)=3 을 곱하여 6가지로 연산한다.
위의 7과 같이 4이상의 수가 자르는 index가 되며 0의 경우는 앞자리와 함께 비교하여 자를 포인트를 결정하게 된다. 또한 90,80과 같이 현재 위치가 0이고 앞 자리와 합한숫자가 34가 넘을경우 가짓수를 0으로 한다.
코드 보기 접기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package Dinamic;
import java.util.Scanner ;
//정올 Q1407 숫자카드
public class Q1407 {
static int [] result;
static String number;
public static void main(String [] args) {
Scanner sc = new Scanner (System .in );
number = sc.nextLine();
result = new int [number.length ()+ 1 ];
function();
}
public static void function(){
result[0 ] = 1 ;
result[1 ] = 1 ;
for (int i = 2 ;i< result.length ;i+ + ){
//f(n) = f(n-1)-f(n-2)+f(n-2)*2
//f(n)은
//n-2의 숫자조합중 끝자리가 2자리 조합의 갯수는 f(n-1)에서 f(n-2)를 뺀값
//n-1의 숫자조합중 끝자리가 1자리 조합의 갯수는 f(n-2)이고 이 숫자조합은 2가지 가짓수를 만들수 있으므로 *2
//위 두가지를 더하면 f(n) = f(n-1)-f(n-2) + f(n-2)*2 이다
//위 식을 정리하면 f(n) = f(n-1)+f(n+1)이다.
result[i] = result[i- 2 ]+ result[i- 1 ];
}
int sum = 1 ;
int start = 0 ;
for (int i = 0 ;i< number.length ();i+ + ){
if (i- 1 > 0 & & number.charAt (i)= = 48 & & number.charAt (i- 1 )> 51 ){
System .out .println (0 );
return ;
}
if (i+ 1 = = number.length ()){
// System.out.println(i+" : "+"sum :"+sum+", "+(i-start+1));
sum = sum * result[i- start+ 1 ];
}else if (number.charAt (i)= = 48 ){
sum = sum * result[i- 1 - start+ 1 ];
start = i+ 1 ;
}
else if (number.charAt (i)> 51 ){//숫자가 3보다 클시
sum = sum * result[i- start+ 1 ];
start = i+ 1 ;
// System.out.println(i+" : "+"sum :"+sum+", "+(i-start+1));
}else if (number.charAt (i)= = 51 ){//34이상
if (number.charAt (i+ 1 )> 52 ){
// System.out.println(i+" : "+"sum :"+sum+", "+(i-start+1));
sum = sum * result[i- start+ 1 ];
start = i+ 1 ;
}
}
}
System .out .println (sum);
}
}
cs
접기
function 함수 속 if문을 보자
number. charAt (i) = = 48 & & number. charAt (i - 1 ) > 51
현재 숫자가 0이고 앞 숫자가 4이상일때 40,50,60등의 숫자가 나타나므로 가능한 가짓수는 0개이다.
i + 1 = = number. length ()
마지막 숫자에 다달았을시 조건
number. charAt (i) = = 48
숫자가 0이었을시, 계산이 약간다르다 현재위치가 아닌 이전위치까지의 갯수를 세고 f(n)을 구한다.
number. charAt (i) > 51
숫자가 3보다 클 시
생각보다 까다로웠던 문제다 f(n)을 구하는 것부터 조건문을 작성하는 것까지 까다로웠다.
