[백준 11055, 11722, 11054][파이썬] 증가, 감소하는 수열 dp 문제
백준 문제 11055, 11722, 11054는 비슷한 문제로 묶어서 풀이를 해보려한다. 먼저 11055번 문제이다. https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 이 문제를 푸는 가장 간단한 알고리즘은 이중 반복문을 사용하여 전부 조사하는 방법이다. 이 방법도 좋은 방법이지만 더 빠른 방법을 사용해보려 한다. 간단하게 1,3,2,6,9 라는 수열이 있다고 해보자. 이 수열의 값을 배..
2023. 1. 11.
[백준][파이썬] 쉬운 계단 수 10844
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net n=1 : (1) n=2 : (1, 2), (1, 0) n=3 : (1, 2, 1), (1, 2, 3), (1, 0, 1) . . . 자세히 보면 어떠한 규칙이 존재한다. 먼저 n이 1에서 2로 넘어갈 때를 보자. n=1 에서 1 하나만 존재하는데 문제의 조건을 만족하기 위해서는 1다음에 1+1과 1-1이 존재해야한다. n이 2에서 3으로 넘어갈 때도 보자. (1, 2)에서 문제를 조건을 만족하기 위해서는 1, 2 다음에 2+1과 2-1이 존재해야한다. (1, 0)에서는 1, 0 다음에 0+1과 0-1이 존재해..
2023. 1. 9.
