[백준/Swift] 1904 : 01타일

 

 

• BOJ_1904.swift

• 1904 : 01타일 / 문제 소개
• 풀이 과정
• 코드 구현

https://www.acmicpc.net/problem/1904

1904번: 01타일

1904 : 01타일 / 문제 소개

 

현재 있는 타일은

 낱장 타일 1

 낱장 두개 붙인 타일 00

총 2가지가 존재한다.

낱장 타일 0 은 존재하지 않으므로 01 , 10 은 만들 수 없다.

풀이 과정

 

이 문제를 풀어 나갈 때 규칙을 찾아야 합니다.

 

• N = 1

타일 1 만 사용할 수있습니다. dp[1] = 1 (최대)

• N = 2

타일 1 또는 타일 00 을 사용해서

11 또는 00을 만들 수 있습니다. dp[2] = 2 (최대)

• N = 3

이 경우는 111 001 100 이렇게 세개의 경우가 올 수 있습니다.

 

이때 이전에 구해놨던 최대 케이스를 사용하는 방식으로 두가지 조건을 설정하면 손 쉽게 구할 수 있습니다.

  맨 앞에 타일 1이 오는 경우, 맨 앞에 타일 00이 오는 경우

 

     1. 맨 앞 타일 1이 존재 할

뒤에올 타일은 00 또는 11 두 가지가 존재합니다. 이는 N = 2에서 구했던 최대 경우의 수인 dp[2] = 2의 경우의 수입니다.

 

     2. 맨 앞 타일 00이 존재 할 경우

뒤에 올 낱장 타일은 1만 존재하므로( 001 ) 경우의 수가 1입니다. 이 조건은 맨 처음 N = 1에서 구했던 dp[1] = 1인 경우의 수입니다.

 

이렇게 dp[3] = dp[2] + dp[1]을 통해서 구할 수 있습니다.

 

• N = 4

이 경우도 마찬가지로 앞에 1이 오는 경우 00 이 오는 경우에 따라 남은 자리수가 존재하는데

1의 경우 3자리는 N = 3일때 최대값 dp[3] 

00의 경우 남은 2자리 N = 2 일때 최대값 dp[2]

 

dp[4] = dp[3] + dp[2] 로 구할 수 있습니다.

dp[n] = dp[n-1] + dp[n-2]

최종적으로 이 식을 적용시킬 수 있습니다.

 

코드 구현

 

import Foundation

func BOJ_1094()
{
    var n  = Int(readLine()!)!
    var dp = [0,1,2]
    if n > 2
    {
        for i in 3...n
        {
            dp.append((dp[i-1] + dp[i-2]) % 15746 )
        }
    }
    print(dp[n])
}
BOJ_1094()

 

visit my github