Problem Solving/Java

백준 2193 이친수 동적계획법 활용 2가지 풀이 ( Java )

TakeKnowledge 2019. 11. 1. 10:08
반응형
 

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되

www.acmicpc.net

 

- 2차원 배열 활용

 

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
import java.io.*;
 
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 n = Integer.parseInt(br.readLine());
 
        long[][] pinaryNumber = new long[n + 1][2];
 
        pinaryNumber[1][0] = 0;
        pinaryNumber[1][1] = 1;
        // 기저사례 세팅
 
        if (n >= 2) {
            pinaryNumber[2][0] = 1;
            pinaryNumber[2][1] = 0;
 
            for (int i = 3; i <= n; i++) {
 
                pinaryNumber[i][0] = pinaryNumber[i - 1][1] + pinaryNumber[i - 1][0];
                // 처음이 아니면 1과 0 모두 올 수 있다
 
                pinaryNumber[i][1] = pinaryNumber[i - 1][0];
                // 마지막에 1이 오면 앞에는 0만 올 수 있다
            }
        }
 
        long answer = pinaryNumber[n][0] + pinaryNumber[n][1];
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

- 1차원 배열 활용

 

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
import java.io.*;
 
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 n = Integer.parseInt(br.readLine());
 
        long[] pinaryNumber = new long[n + 1];
 
        pinaryNumber[1] = 1;
 
        // 기저사례 세팅
 
        if (n >= 2) {
            pinaryNumber[2] = 1;
 
            for (int i = 3; i <= n; i++) {
 
                pinaryNumber[i] = pinaryNumber[i - 1] + pinaryNumber[i - 2];
                // pinaryNumber[i] = i 자리 이친수의 갯수
                // pinaryNumber[i-1] = 마지막에 온 숫자가 0일 경우 그 전에 온 숫자는 알 수 없다
                // pinaryNumber[i-2] = 마지막에 온 숫자가 1일 경우 그 전에는 0만 올 수 있다. 그 전에 온 숫자는 알 수 없다
                // 그러니까 i-2일때는 01을 한 세트로 묶어서 생각한다
            }
        }
 
        long answer = pinaryNumber[n];
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

두 방식 모두 n으로 1일때를 간과하고 if (n >= 2) 처리를 안해줬다가 한참 헤맸다

아아 PS.. 그것은 헤맴의 연속..

반응형