케이스윔의 개발 블로그

문제 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라는 것만 ..

문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.) 입력과 출력 첫째줄에 n, k가 주어지고 n개의 동전가치가 차례대로 들어오며 k는 만들어야하는 가치의 금액이다 출력은 사용한 동전의 최소 개수이다 풀이 전에 2원 6원 8원으로 k원을 만드는 비슷한 문제들을 풀어본적이 있는데 이건 아예 항상 사용할 수 있는 동전의 개수도 다르고 종류도 다르다길이가 k인 배열을 만들고 각 금액을 만드는 최소 개수를 저장해 나가면서 k자리의 값을 을 구한다불가능한 경우에는 -1을 출력하므로 배열은 -1로 초기화한다n개의 동전이 들어오면..