링크https://www.acmicpc.net/problem/11057 문제오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. 입력첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. 출력첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다. 예제 입력 11 예제 출력 110 예제 입력 22 예제 출력 255 예제 입력 33 예제 출력 3220 아이디어 ..
링크https://www.acmicpc.net/problem/11722 문제수열 \(A\)가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 \(A\) = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 \(A\) = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력첫째 줄에 수열 \(A\) 의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 \(A\) 를 이루고 있는 \(A_i\)가 주어진다. (1 ≤ \(A_i\) ≤ 1,000) 출력첫째 줄에 수열 \(A\)의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 예제 입력 16 10 30 10 20 20 10..
링크https://www.acmicpc.net/problem/1149 문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1..
링크https://www.acmicpc.net/problem/2193 문제0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 출력첫째 줄에 N자리 ..
링크https://www.acmicpc.net/problem/12865 문제이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력첫 줄에 물품의 수 N(1 ≤ N ..
링크https://www.acmicpc.net/problem/11051 문제자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\) 를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 \(N\)과 \(K\)가 주어진다.(1≤\(N\)≤1,000,0≤\(K\)≤\(N\)) 출력\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다. 예제 입력 15 2 예제 출력 110 아이디어 스케치이항 계수를 동적계획법 알고리즘을 이용해서 푸는 문제이다. 동적계획법 알고리즘을 사용하기 전 기반 상황과 일반 상황을 살펴보겠다. 기반 상황이란 답이 이미 알려진 가장 작은 부분 문제이고, 일반 상황이란 기반 상황을 제외..
