[백준 - C#] 1904번 01타일

문제링크

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

1904번: 01타일

 

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다.
그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다.
예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.
단 타일들은 무한히 많은 것으로 가정하자.

조건

시간제한 : 0.75초
메모리 제한 : 256 MB

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

 

문제정리

1. 타일은 1과 00으로 2개만 존재합니다.
2. 자연수 N이 주어졌을 때 타일 2개로 만들 수 있는 조합의 가짓수를 파악해야합니다.
3. N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력해야합니다.
4. N은 1보다 크거나 같고 1,000,000 작거나 같습니다.

이번 문제의 경우 주어진 두가지 수의 타일을 가지고 자연수 N이 주어졌을 때 만들 수 있는 가짓수를 파악해야합니다.

문제를 풀기전 동적프로그래밍이라는 것을 알았고, 아무 생각없이 1부터 6까지 경우의 수를 써보았습니다.

// 1 = 1
// 2 = 00 11
// 3 = 001 100 111
// 4 = 0011 1100 1111 0000 1001
// 5 = 00111 11100 11111 10000 00001 11001 10001 10011
// 6 = 001111 111100 111111 110000 000011 111100 001111 110011 1001111 111001 001001 001100 000000

가짓수 : 1 -> 2 -> 3 -> 5 -> 8 -> 13

유심히 조건을 찾다보니 먼가 익숙한 숫자의 배열이 보였습니다. 

바로 저번에 풀었던 피보나치의 수열 문제였습니다.

참고 : https://bokhead.tistory.com/95

[백준 - C#] 24416번 알고리즘 수업 - 피보나치 수 1

위에 문제를 보고 수식을 풀이하여 간단하게 풀 수 있었습니다.

여기서 주의할점 2가지가 있는데,

 

하나는 N이 1인 경우도 있는데 dp[2]를 접근하는 경우 OutOfRange 예외 상황을 발생시켜 실패하였습니다.

또다른 하나는 15746을 나누라는 문제의 의도입니다.

15746의 경우 나누지 않게되면 int와 long조차도 넘는 큰 수가 발생할 가능성이 있기 때문에 나누었습니다.

 

몇 문제 안풀어 봤지만 역시 동적프로그래밍은 어렵습니다..

 

C# 코드

static void Main(string[] args)
{
    //  https://bokhead.tistory.com/
    // 1904
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
 
    int[] dp = new int[N + 1];
 
    dp[1] = 1;
 
    // N이 1인 경우 dp[2]을 참조하게 되어 OutOfRange가 발생합니다.
    if (N > 1)
    {
        dp[2] = 2;
 
        for (int i = 3; i <= N; i++)
        {
            // 문제에서 15746을 나눈 나머지를 출력하라고 합니다.
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }
    }
 
    writer.WriteLine(dp[N]);
 
    writer.Close();
    reader.Close();
}

 

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.