ㅇㅅㅎ

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 이 문제는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence) 문제로 동적 계획법으로 풀 수 있는 문제입니다. 코드를 보시려면 더보기를 누르시면 됩니다. 더보기 전체 코드 # 백준 11053 가장 긴 증가하는 부분 수열 def solve(N, LIS): dp = ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 이 문제는 점화식을 이용하여 풀면 되는 문제입니다. 문제 풀이를 보시려면 더보기를 클릭하시면 됩니다. 더보기 포도주 시식 이 문제에서..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 예시에서 입력이 1이면 즉, N이 1일 경우는 출력이 9이다. 다른 예시를 살펴보면 입력이 2이면 출력이 17이다. 길이가 2인 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98이다. 이 개수를 1,000,000,000으로 나누면 17이 됩니다. 우선 숫자를 가지고 자릿수를 늘려가면서 가능한 계단 수를 확인해 보겠습니다. 위의 그림을 표로 정리해보면 아래와 같습니다. 숫자|단계 1 2 3 4 5 6 0 1 1 2 3 6 ... 1 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X를 10이라고 가정하고 위의 3가지 규칙을 적용하면 아래 그림과 같습니다. 이것을 단계별로 나누면 3단계에서 1을 처음 볼 수 있습니다. X를 N이라고 가정하고 단계를 리스트에 저장하는 방법은 아래와 같습니다. lst = [] for i in N: # 규칙 3 lst.append(i - 1) # 규칙 1 if i % 3 == 0: lst.append(i // 3) # 규칙 2 if i % 2 == 0: lst.append(i // 2) 이 리스트에 중복 값이 있을 수 있기 때문에 중복을 제거해 주어야 합..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 문제 풀이를 보시려면 더보기를 클릭하시면 됩니다. 더보기 계단 오르기 계단을 오르는 규칙에 유의하면서 점화식을 만들어 주면 됩니다. 규칙 1. 계단은 1 ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 더보기 문제 풀이 입력을 아래와 같이 했을 경우 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 최댓값은 아래의 그림과 같습니다...