1904번 01타일 , 9461번 파도반 수열

코딩테스트 : 1094번 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

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

출력

 

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

public class BackJoon
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int answer = DP(n);
        Console.WriteLine(answer%15746);
    }


    static int DP(int n)
    {
        if (n == 1) return 1; 
        
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
        {
            if (i % 2 == 0)
            {
                dp[i] = dp[i - 1] + 2;
            }
            else
            {
                dp[i] = dp[i - 1] + 1;
            }
        }
        return dp[n];
    }
}

 

일단 이렇게 풀었다, i가 짝수일 때와 홀수 일 때 의 수가 다른 것 같아서.

 

흠.. .. . . . 조금 더 점화식을 통일해서 쓰고 싶어서 한참 고민하다 경우의 수 정리를 AI에게 맡겼다. 

내가 직접 세었던 것과 다른 결과가 나와서 당황했다. 

실수를...했나보다. 그냥 피보나치랑 똑같은 점화식이다. 

 

왜 내가 못풀었냐고 하니, 전에 있는 경우의 수들에서만 다음 경우의 수를 계산했다. 

결국 중요한 사실은 맨 뒤에 1 혹은 00만이 나올 수 있는 상황이고, 점차 N의 증가해가면서 1 혹은 00을 뒤에 붙이면 

아무리 N이 많아져도 똑같이 수행할 수 있다는 사실이다. 

그러니 00을 붙일 수 있는 경우 ( dp(N-2)) 와 1을 붙일 수 있는 경우의 수 ( dp(N-1)) 을 더해주면 된다. 

 

public class BackJoon
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int answer = DP(n);
        Console.WriteLine(answer);
    }


    static int DP(int n)
    {
        if (n == 1) return 1; 
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)
        {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }
        return dp[n];
    }
}

 

중간에 15746을 나눠주지 않으면 틀린다. 

물론 이 문제에서는 모든 배열을 다 저장할 필요는 없다. -1번째와 -2번째 배열만 저장해주면 된다. 

 

 

코딩테스트 :  9461번 파도반 수열  

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

using System.Text;

public class BackJoon
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        Dictionary<int, int> dic = new Dictionary<int, int>();
        dic.Add(1, 1);
        dic.Add(2, 1);
        dic.Add(3, 1);
        dic.Add(4, 2);
        dic.Add(5, 2);
        dic.Add(6, 3);
        dic.Add(7, 4);
        dic.Add(8, 5);
        for (int i = 0; i < n; i++)
        {
            int temp = int.Parse(Console.ReadLine());
          sb.AppendLine(DP(temp,dic).ToString());  
        }
        Console.WriteLine(sb.ToString());
    }


    static int DP(int n, Dictionary<int, int> dic)
    {
         if ( dic.ContainsKey(n)) return dic[n];

         int temp = DP(n -1,dic) + DP(n - 5, dic);
         dic.Add(n, temp);
         return temp;
    }
}

 

우선 예시까지는 내 식이 성립한다. 

5
17
18
19
20
21

 

아무리 생각해도 내 답이 맞는 것 같은데 안되길래 ,GPT한테 물어봤다. 

 

그래서 그림을 보면서 다시 점화식을 짜 봤는데 진짜 내가 맞는것 같은데 ??? 해서 다시 했다. 

 

 

ㅇㅣ친구 허허

그럼.. 왜 틀린거지 ? 하고 혹시나 해서 100을 넣어봤다. 

2
6
100
3
-203165375

자료형이...틀렸구나... 

using System.Text;

public class BackJoon
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        Dictionary<long, long> dic = new Dictionary<long, long>();
        dic.Add(1, 1);
        dic.Add(2, 1);
        dic.Add(3, 1);
        dic.Add(4, 2);
        dic.Add(5, 2);
        dic.Add(6, 3);
        dic.Add(7, 4);
        dic.Add(8, 5);
        for (long i = 0; i < n; i++)
        {
            long temp = long.Parse(Console.ReadLine());
          sb.AppendLine(DP(temp,dic).ToString());  
        }
        Console.WriteLine(sb.ToString());
    }


    static long DP(long n, Dictionary<long, long> dic)
    {
         if ( dic.ContainsKey(n)) return dic[n];

         long temp = DP(n -1,dic) + DP(n - 5, dic);
         dic.Add(n, temp);
         return temp;
    }
}

 

생각보다 숫자가 커 지는 속도가 느리길래 ,int형으로 충분히 감당할 수 있을것 같았는데 ... ㅎ

다음부터는 스스로의 생각에 확신을 갖고 다시 한 번 생각해야지.