케이스윔의 개발 블로그

문제2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력은 2*n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 풀이전에 풀었던 2*n 타일링(11726번) 문제랑 거의 똑같은거 같은데 오늘 너무 문제 풀기싫으니까 동기부여용으로...다시 푼다f(n)= 2*n 직사각형을 채우는 방법의 수f(1) = 1f(2) = 3 f(3) = f(2) + f(1)*2f(4) = f(3) + f(2)*2f(n) = f(n-1)+f(n-2)*2 ->f(n-2)에 대해서 나란히 누워붙이는 경우+2*2 타일쓰는경우라서 2가지 코드dp[1]=1;dp[2]=3; ..

문제 45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째줄에 N이 주어진다 N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다정답은 1,000,000,000으로 나눈 나머지를 출력한다 풀이 f(n, i) = 길이가 n인 i로 시작하는 계단 수가 몇개인지f(1, 1) =1 f(1, 2) =1 .... f(1, 9)=1 f(2, 1) = f(1,2) -> 길이가 2인 1로 시작하는 계단수는 길이가 1일때 2로 시작하는 계단수에 1을 붙이는거f(2, 2) =..

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째, 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번째 계단을 밟고 이어 ..

문제2*n 크기의 직사각형을 1*2, 2*1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력과 출력첫째줄에 n이 주어지면(1

문제오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이 때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력과 출력N(1

문제 강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다.해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다.붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다.붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개, 2개로 붕어빵을 팔면 되기 때문이다.1개 팔 때의 가격이 5, 2개는 2, 3개는 8, 4개는 10 인 경우에는 20이 된다. 1개, 1개, 1개, 1개로 붕어빵을 팔면 되기 때문이다.마지막으로, 1개 팔 때의 가격이 3, 2..

문제 지원이에게 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 등..

문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이를 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 1. 이친수는 0으로 시작하지 않는다.2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10,100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1≤N≤90)이 주어졌을 때 N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력과 출력 첫째줄에 N이 주어지면 N자리 이친수의 개수를 출력 풀이 다이나믹 프로그래밍 문제만 찾아풀고있어서 이 문제가 DP라는 것만 ..