[알고리즘 PS] 백준 1904번 01 타일 자바 문제 풀이

문제

해당 포스팅은 백준의 1904번 01 타일 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

문제

해결법

우선 문제를 제대로 파악해보자.

타일이고 뭐고를 떠나서 우리는 수열을 만들어야 한다.

근데 그 수열을 만들기 위해서 주어지는 수가 2가지 종류이다.

1. 1
2. 00

그리고 길이가 n인 수열을 만들어야 한다.

예를 들어서 길이가 n인 수열을 여러개 만들어서 규칙을 찾아보자.

tile(1) = 1
tile(2) = 11, 00
tile(3) = 100, 001, 111
tile(4) = 1000, 1001, 0011, 1100, 1111
...

 

여기서 좀 생각해보자.

 

만약 100의 길이를 갖는 타일을 만든다고 하면, 어떻게 할까?

타일의 종류는 2가지, 00과 1이므로 각각의 길이가 2와 1이다.

그럼 100의 길이를 갖는 타일을 만들려면 98개의 타일에서 00 타일을 더해서 만들 수 있는 경우와 99개의 타일에서 1 타일을 더해서 만들 수 있는 경우를 합치면 되지 않을까?

그렇다.

정답이다.

근데 조건이 하나가 더 추가된다.

15746을 나눈 나머지를 출력하라고 했다.

이는 아마 수의 범위가 너무 커져서 해당 조건을 추가한 것이다.

단순히 출력문에 15746을 모듈러하면 수를 계산하여 저장하는 내부 배열 tile 에서 int보다 큰 값이 들어가 오버플로우가 발생해 오답을 낼 것이다.

 

그러므로 tile의 값을 구하는 매 연산마다 모듈러를 추가해주자.

코드로 가기 전에 잠깐 이것 하나만 짚고 넘어가자 중요하다.

나도 처음엔 그랬고 많은 사람들이 해당 문제를 직접 가지수를 계산해본 뒤 피보나치 같은 수열이 나와서 해당 식을 점화식으로 도춣해서 문제를 풀곤한다.

하지만 이런 접근 방법은 매우 좋지 않다고 생각한다.

동적 계획법으로 풀릴 수 있는 문제의 대다수는 점화식이 존재한다고 하더라도 우리가 문제의 입출력을 직접 써보며 항상 점화식을 구할 수 있는 것은 정말 힘들다.

그러므로 좀더 좋은 알고리즘을 해결하고 생각해내기 위해서는 힘들더라도 왜 이런 점화식이 나왔는지, 이런 점화식을 어떻게 도출해 냈는지를 알 수 있어야 한다.

 

정답 코드

Dynamic Programming 은 특성상 2가지의 방법으로 해결할 수 있다.

1. Top Down
2. Bottom Up

두 방법으로 모두 풀어보도록 하자.

Top Down

TopDown 방법의 특징이라고 한다면 일단 점화식을 그대로 사용할 수 있다는 것이다.

하지만 점화식을 그대로 사용한다면 해당 문제는 중복 계산이라는 치명적인 비효율 덩어리가 될 것이다.

그러므로 중복 계산을 없애는 Memoization 과정을 추가해주어야 한다.

import java.io.*;

public class Main {

  private static int[] tile; // memoization 배열

  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());

    tile = new int[10000001];

    bw.write(String.valueOf(tiling(n)));

    bw.flush();
    bw.close();
  }

  private static int tiling(int n) {
    if(tile[n] > 0) return tile[n]; // 이전에 계산했던 값이라면 중복 계산을 하지 않는다.

    if (n == 1) return tile[1] = 1;
    else if (n == 2) return tile[2] = 2;
    else if (n == 3) return tile[3] = 3;
    else {
        tile[n] = tiling(n-1) + tiling(n-2);
        return tile[n] %= 15746;
    }
  }
}

 

Bottom Up

 

Bottom up은 점화식의 논리 자체를 반복문으로 변형하는 것이다.

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[] tile = new long[1000001];

    tile[1] = 1; tile[2] = 2; tile[3] = 3;
    if(n > 3) {
      for(int i = 3; i <= n; i++) {
        tile[i] = tile[i-1] + tile[i-2];
        tile[i] %= 15746;
      }
    }
    bw.write(String.valueOf(tile[n]));

    bw.flush();
    bw.close();
  }
}

Top Down 대신 Bottom up 을 사용한다면 함수 호출 공간이 작아지므로 공간적으로 봤을 때 이득을 취할 수 있다.

 

하지만 변수 사용이 많아지고 그에 따라 자연스럽게 변경될 수 있는 위험도가 증가되며 (알고리즘 문제풀이를 떠나서) 직관적이지 않게 된다.

 

각각의 장단점은 분명 존재하니 비교해보고 더 잘 어울리는 것을 선택하면 좋을듯 하다.

 

하지만 연습때는 왠만하면 두 방법을 다 써보도록 하자.

 

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.