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