문제 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 레슨 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다. 강토의 각 레슨의 길이가 ..
문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 1..
문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 출력 입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다. 문제풀이 딱 보면 작은 문제가 반복되어서 큰 문제를 풀 수 있는 전형적인 다이나믹 프로그래밍 문제라는 것을 알 수 있다. 이런 문제라는 것을 눈치 챘다면, 점화식이 어떻게 될지를 생각해봐야 한다. 점화식을 생각하는 방법은 생각보다 간단했다. 경우를 나누고, 그 경우를 메모리제이션을 통해서 풀 수 있게 생각을 하면 된다. 나 같은 경..
문제 단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만 이루어져 있다. 단어와 다른 문자(마침표, 숫자, 심볼, 등등등...)로 이루어진 글이 주어졌을 때, 가장 긴 단어를 구하는 프로그램을 작성하시오. Apple의 길이는 5, son-in-law는 10, ACM-ICPC는 8이다. 입력 입력은 여러 줄, 문단으로 이루어져 있다. 하지만, 10,000글자를 넘지 않는다. 단어의 길이는 100을 넘지 않는다. E-N-D는 입력의 마지막을 의미한다. 출력 가장 긴 단어를 소문자로 출력한다. 가장 긴 단어가 여러개인 경우에는 글에서 가장 먼저 나오는 것을 출력한다. 문제풀이 이 문제는 경우를 정확히 나누는 것으로부터 문제 풀이가 시작이 된다. 경우를 먼저 간단히 나누면 다음과 같다. 1. 단어는 반드시 알파..
문제 수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오. 즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다. 입력 첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다. 출력 첫째 줄에 답을 출력한다. 문제풀이 나는 다음과 같은 아이디어로 시간을 단축해서 풀었다고 생각을 했는데, 다른 분들 답안 제출하신 것들을 보니 O(n) 혹은 O(nlogn) 수준으로 시간복잡도를 줄일 수 있을 것으로 보인다. 내가 푼 방법은 굉장히 단순했는데, 아이디어는 이렇다 ((a1-..