[알고리즘 문제] 2 x N 타일링 (programmers)

2 x N 타일링

 프로그래머스로 문제 풀러 가기 

[문제]

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 2xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.

보드판의 길이 N이 주어질 때, 2xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.

예를들어 N이 7일 경우 아래 그림이 타일을 배치할 수 있는 한 경우입니다.

단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 가로로 배치하는 경우와 세로로 배치하는 경우가 있을 수 있으므로 2를 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.

[나의 풀이]

말로 하기가 애매한데 타일을 전부 다 세로로 붙여놓았다고 하고 얘네를 2칸씩 가로로 바꿔 붙이는 방법이 몇 가지 인지를 구하라는 것과 같습니다.

( || 를 세로배치 〓 를 가로배치 라고 하겠습니다.)

예를 들어 6칸인 경우

가로 배치한 타일들이 0쌍 일 때

'||||||'  경우의 수 1가지.

 

가로 배치한 타일들이 1쌍 일 때

'||||〓', '|||〓|', '||〓||', '|〓|||', '〓||||' 경우의 수 5가지.

가로 배치한 타일들이 2쌍 일 때

'||〓〓', '|〓|〓', '〓||〓', '|〓〓|', '〓|〓|', '〓〓||' 경우의 수 6가지.

가로 배치한 타일들이 3쌍 일 때

'〓〓〓' 경우의 수 1가지.

이처럼 가로로 배치한 타일들을 나열하는 경우의 수를 구하는 것과 같습니다.

따라서 경우의 수는 다음과 같다는 것을 알 수 있습니다.

N	경우의 수	결과
1		1
2		2
3		3
4		5
5		8
6		13
7		21
8		34
n

이제 답이   라는 것은 알았습니다.

( ※ n이 짝수일 때와 홀수일 때가 조금 다르지만 어차피 자바에서의 나누기 연산은 나머지를 버림하기 때문에 문제 없습니다. )

이걸 자바 코드로 구현하면 됩니다.

우선 조합(nCr) 을 연산하는 메소드를 구현합니다.

 

// 팩토리얼 구하기
public int getFactorial(int n) {
    if(n<2)
        return 1;
    return n*getFactorial(n-1);
}
  
// (N * N-1 * ...) 를 cnt 번 곱한 값 구하기
public int getFacByCnt(int n, int cnt) {
    int res = 1;
    for(int i=0; i<cnt;i++) {
        res *= n-i;
    }
    return res;
}
 
// 조합(nCr) 을 연한하는 메소드
public int getCombination(int n, int r) {
    r = (r > n/2) ? n-r : r;
 
    int res = getFacByCnt(n,r)/getFactorial(r);
 
    return res;
}

이제 최종적으로 n 을 입력받아 경우의 수를 return 하는 메소드를 구현합니다.

// 시그마 연산을 진행할 메소드
public int tiling(int n) {
    int result = 0;
 
    for(int k=0; k<=n/2; k++) {
        answer += getCombination(n-k, k);
    }
 
    return answer;
}

이제 완성인 것 같지만 큰 수가 입력됬을 경우 처리를 못해주기 때문에 오답 결과를 받았습니다.

문제에 이런 내용이 있습니다.

 "하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다."

int 대신 long으로 처리해도 팩토리얼 연산을 처리하지 못했습니다. 그래서 BigInteger 클래스를 사용했습니다.

결과는 정답처리~

import java.math.BigInteger;

class TryHelloWorld {
    public int tiling(int n) {
    BigInteger answer = new BigInteger("0");

    for(int k=0; k<=n/2; k++) {
      answer = answer.add(getCombination(n-k, k));
    }    
    if(answer.compareTo(BigInteger.valueOf(100000)) >= 1) {
      answer = answer.remainder(BigInteger.valueOf(100000));
    }    
        return answer.intValue();
    }

    public static void main(String args[]) {
        TryHelloWorld tryHelloWorld = new TryHelloWorld();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(tryHelloWorld.tiling(2));

    }

  // 팩토리얼 구하기
    public BigInteger getFactorial(BigInteger n) {
    if(n.compareTo(BigInteger.valueOf(2)) == -1)
      return BigInteger.valueOf(1);
    return n.multiply(getFactorial(n.subtract(BigInteger.valueOf(1))));
  }

  // (N * N-1 * ...) 를 cnt 번 곱한 값 구하기
  public BigInteger getFacByCnt(int n, int cnt) {
    BigInteger res = new BigInteger("1");
    for(int i=0; i<cnt;i++) {
      res = res.multiply(BigInteger.valueOf(n-i));
    }    
    return res;
  }

  //조합(nCr) 을 연산하는 함수
  public BigInteger getCombination(int n, int r) {
    r = (r > n/2) ? n-r : r;    
    BigInteger res = getFacByCnt(n,r).divide(getFactorial(BigInteger.valueOf(r)));    
    return res;
  }
}

하지만 다른 사람 풀이를 보고 자괴감이...

(피보나치 수열이였다...)

[다른사람 풀이]

Isaac Ahn

class TryHelloWorld {

    public int tiling(int n) {
        int a = 1;
        int b = 1;
        for (int i = 0; i < n - 1; i++) {
            int fib = (a + b) % 100000;
            a = b;
            b = fib;
        }
        return b;
    }

    public static void main(String args[]) {
        TryHelloWorld tryHelloWorld = new TryHelloWorld();
        //아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.print(tryHelloWorld.tiling(2));
    }
}

좋아요

• 

  음.. 길이가 1늘어났을때 직전 경우에서 한가지 방법밖에 없고 그전(2번 전)의 경우에서 한가지 방법밖에 없습니다. ===> 1번전의 경우의수 + 2번전의 경우의수 = 1칸 늘어난 현재 경우의수 ― 우제민 2017.10.8 23:54

• 

  n>=3일 때, 맨 왼쪽에 타일 하나가 오는 경우의 수를 보면 세로, 가로 두 가지 경우가 있는데요. 가로로 하나 놨을 때 나머지 n-2열에 타일을 나열할 때 와 세로로 하나 놨을 때 n-1의 타일을 나열 하는 경우의 수는 관련이 없다? 독립? 이니까 결국은 Tn-2 + Tn-1 = Tn이 되네요. ― 임택 2017.9.15 12:19

• 

  안녕하세요. 풀이보고 이해가 잘 되지않아 질문남겨요. 피보나치 수열로 정답을 도출하신 분들께서는 answer가 피보나치 수열을 따라간다는걸 어떻게 도출할 수 있으셨나요? 증명과정이 수식으로 도출되는지 궁금합니다. ― 하창우 2017.9.9 00:47