CEO

문제 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..

문제 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 문제 풀이 기존에 푼 문제 중 11053 가장 긴 증가하는 부분 수열의 풀이를 이해하고 있다면, 이 문제는 쉽게 풀 수 있다. 기존의 문제는 가장 긴 수열의 길이를 카운트 하였지만, 이 문제는 수열이 증가한다면 이전의 값들을 중첩시키면 문제의 답을 찾을 수 있다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()..

문제 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 풀이 삼각형의 특성을 이해하면 쉽게 풀 수 있는 문제이다. 삼각형 좌/우측 변에 있는 값들은 위의 값 중 하나의 값만 더하면 되지만 각 끝 변이 아닌 경우는 2개의 값을 받게 된다. 따라서 좌/우측 변을 제외하고 나머지는 가장 큰 값을 누적해주면 문제를 풀 수 있다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()) triangl..

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 포도주 마셨을 때 가장 많이 마시는 경우를 찾는 문제이다. 문제의 제한사항으로 연속해서 3잔 이상의 포도주를 마실 수 없다. 처음부터 세잔의 와인을 마실 경우 마실 수 있는 포도주는 다음과 같다. OXO : 중간 와인을 마시지 않는 경우 OOX : 세 번째 와인을 마시지 않는 경우 XOO : 첫 번째 와인을 마시지 않는 경우 즉, 이전 와인과 현재 와인을 마시는 경우와 전전의 와인과 현재 와인을 마시는 경우, 현재 와인을 마시지 않는 경우로 나뉘어..

문제 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 문제 풀이 스티커를 제거 할 때 다음과 같은 규칙이 적용된다. 변을 인접하고 있으면 동시에 스티커가 제거되어 선택할 수 없으므로 대각선으로 선택하여야 한다. 스티커의 점수가 최대가 되기 위해서는 대각선의 점수를 합하여 최대 값을 찾으면 된다. 첫 번째 행에서 시작하게 된다면 `↘↗↘↗` 와 같이 스티커를 선택하게 된다. 이와 반대로 두 번째 행의 경우 `↗↘↗↘` 와같이 스티커를 선택하게 된다. 첫 번째 열과 두 번째 열은단순히대각선의합을구하면되지만 단순히 대..

문제 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 풀이 아홉 난쟁이 중에 7명을 선택하였을 때 키의 합이 100이 되는 경우를 찾는 문제이다. 주어진 9명의 난쟁이들을 7명으로 뽑을 수 있는 조합을 찾고 이 중에 키의 합이 100인 경우를 반환하면 된다. 코드 from itertools import combinations if __name__ == '__main__': dwarfs = [0] * 9 for idx in range(9): dwarfs[idx] = int(input()) for case in co..