HOIT_B

[문제] www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net [접근] 먼저 1~5일 때 까지를 찾아봤다. N=1 =>1 N=2 =>1 N=3 =>2 N=4 =>3 N=5 =>5 보니까 아주 익숙한 피보나치 수들이다. 그래서 쉽게 dp[i] = dp [i-1]+dp [i-2]라는 식을 찾을 수 있었다. [코드] using System; class dp{ static void Main(){ int n = int.Parse(Console.ReadLine()..

[문제] www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net [ ] 쉬운 계단수와 비슷하게 접근했다. 마지막 자릿수를 기준으로 경우의 수를 찾았다. N=2 일 때 길이 2 끝자리 1이면 01 11 -> 2가지 길이 2 끝자리 2 이면 02 12 22 -> 3가지 길이 2 끝자리 3 이면 03 13 23 33 -> 4가지 이런 식으로 반복해서 6까지 구해본 후 규칙을 찾아봤다. N=2 이고 끝자리 수가 4 => N=1일 때 끝자..

[문제] www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net [ ] 처음엔 n이 1일 때부터 방법의 수를 찾아서 규칙을 찾으려 했다. 위의 방법에서 규칙을 찾을 수 있긴 했지만 경우의 수를 잘못 찾았을 경우에 시간이 몹시 오래 걸리게 된다. 식을 찾긴했지만 찝찝해서 다른 방법을 찾아봤다. 길이가 1 남고 타일이 채워지는 경우의 수와 길이가 2 남고 타일이 채워지는 경우의 수를 이용하여 접근하는 방법이다. [코드] using System; class dp{ static void Main(){ ..

[문제] www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [ 규칙찾기 ] n : 1 => 1 n : 2 => 2 n : 3 => 3 n : 4 => 5 n : 5 => 8 2Xn = (n-2) + (n-1) [코드] C# using System; class dp{ static void Main(){ int n = int.Parse(Console.ReadLine()); int[] dp = new int[1001]; dp[1] = 1; dp[2] = 2; for(int i=3; i>..

[문제] www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [ ] dp [n] n : 2,3 배수 x >> min[n-1]+1 n : 2의 배수 >> min[n-1]+1 과 min [n/2]+1중 작은 수 n : 3의 배수 >> min[n-1]+1 과 min [n/3]+1중 작은 수 [의사 코드] n입력 받음 n크기의 dp배열 생성 dp [0]=[1]=0 for(2부터 n까지 반복) dp [i] = dp [i-1]+1 if(2의 배수) min(dp [i] , dp[i/2]+1) if(3의 배수) min(dp[i] , dp [i/3]+1) dp [n] 출력 [코드] using..