CEO

문제 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 메모이제이션을 잘 활용하면, 어렵지 않게 풀 수 있다. 또한 각 N행은 하나의 집을 나타내고 1, 2, 3열은 R, G, B로 칠 할 경우 발생하는 비용을 의미한다. 기본 예제는 그림과 같이 나타낼 수 있다. 집 1(0번 인덱스)은 첫 번째 집이기에 값을 누적시킬 필요가 없다. 따라서 집 2(1번 인덱스)부터는 해당 색상을 선택하였을 때, 이전의 집에서 선택할 수 있는 색상의 값 중 최솟값을 더한다. 이를 통해 집 2에 합산..

문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 풀이 이 문제는 11053 가장 긴 증가하는 부분 수열, 11722 가장 긴 감소하는 부분 수열를 이해하고 있다면 쉽게 풀 수 있다. 특정 지점을 선택하였을 때, 증가하는 부분과 감소하는 부분의 합이 가장 큰 경우를 반환하면 된다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()) nums = list(map(int, stdin.readline().split())) forward = ..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 문제 풀이 이전에 푼 10844 쉬운 계단 수에 대한 풀이와 유사한 방식으로 풀 수 있는 문제이다. 차이점은 0으로 부터 시작할 수 있고 수가 중복되어도 된다는 것이다. 따라서 n에 따른 경우의 수들은 f(n) = f(n - 1) + f(n) 점화식을 통해 구할 수 있다. 이는 3으로 끝나기 위해서는 앞의 숫자들이 0, 1, 2가 되어도 되기 때문에 이는 앞에 구한 경우의 수를 합산해주어야 하기 때문이다. 코드 from ..

문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 문제 풀이 기존의 푼 문제 중 가장 긴 증가하는 부분 수열에서 부등호의 방향만 변경하면, 이 문제는 풀 수 있다. 즉 이전 문제의 풀이를 정확히 이해하고 있다면 비슷하게 응용해서 푸는 문제이므로 어렵지 않게 문제를 풀 수 있다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()) nums = l..