몽상실현개발주의

[BOJ] 1699 / 제곱수의 합 / Python 파이썬 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 주어진 숫자와 제곱수와의 차이를 생각하는것이 문제의 해결 방법이었다. N = 1 -> 1 -> 1 N = 2 -> 1 + 1 -> 2 N = 3 -> 1 + 1 + 1 -> 3 N = 4 -> 2 -> 1 N = 5 -> 2 + 1 -> 2 N = 6 -> 2 + 1 + 1 -> 3 N = 7 ..

[BOJ] 2579 / 계단 오르기 / Python 파이썬 https://www.acmicpc.net/submit/2579/29254021 로그인 www.acmicpc.net 풀이 [BOJ] 2156 / 포도주 시식 과 유사한 문제이다. 포도주 시식 문제의 경우 마신다/마시지 않는다의 경우로 선택하지 않는 경우가 있지만, 이 문제의 경우 해당 index 의 계단을 밟지 않는 경우가 없어 고려되지 않는다. 그래서 현재 index 의 계단을 밟는 경우는 두가지가 된다. i-2 i-1 i ~ O X O ~ X O O N = int(input()) nums = [] for _ in range(N): nums.append(int(input())) dp = [0] * N dp[0] = nums[0] if N > 1..

[BOJ] 1912 / 연속합 / Python https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 연속된 수열 중 가장 큰 합을 갖는 수열의 합을 구하는 문제이다. 현재 index 의 값을 더했을때, 1. 이전의 값보다 더 큰경우는 더하여 기록하고 2. 더 작을 경우는 '수열의 합의 큰 수' 를 구하기 위해 현 위치에서 새로 수열을 시작한다. N = int(input()) nums = list(map(int, input().split())) dp = [..

[BOJ] 11054 / 가장 긴 바이토닉 부분수열 / Python https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 [BOJ] 11053 / 가장 긴 증가하는 부분 수열 과 [BOJ] 11722 / 가장 긴 감소하는 부분 수열 을 동시에 찾는 문제이다. 비교 기준 값의 index 를 기준으로, 왼쪽으로는 가장 긴 증가 부분 수열의 길이를 오른쪽으로는 가장 긴 감소 부분 수열 길이를 찾는 문제이다. index의 오른편의 가장 긴 증가 부분 수열 길이는 이전의 ..

[BOJ] 11722 / 가장 긴 감소하는 부분 수열 / Python www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 [BOJ] 11053 / 가장 긴 증가하는 부분 수열 문제의 연관 문제이다. 조건만 반대로 작성해 주면 된다. N = int(input()) nums = list(map(int, input().split())) dp = [1] * N for i in range(N..

[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 [BOJ] 11053 / 가장 긴 증가하는 부분 수열 의 연관 문제이다. 수열의 길이가 아닌 LIS 부분 수열의 원소 합을 구해야 한다. N = int(input()) nums = list(map(int, input().split())) dp = [1] * N for ..

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 긴 증가하는 부분 수열을 구하는 문제로 LIS 문제라고도 한다. 이중 for 문을 이용하여 현재 index 이전 까지의 수 중에서 현재 수보다 작은 숫자들을 찾고, 작은 수들의 부분 문제 결과 를 이용하여 현재 index 의 문제를 해결 할 수 ..

[BOJ] 2156 / 포도주 시식 / Python www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 주어진 조건에 대한 규칙을 배열을 이용하여 찾을 수 있는 문제이다. i 번째 포도주 선택에 대한 경우의 수는 다음과 같다. ~ i-3 i-2 i-1 i ~ O O X ~ O X O ~ X O O 위의 세 경우 중 가장 양이 커질 경우를 선택하면 된다. A = dp[i-1] B = wine[i] + dp[i-2p] C = wine[i] + wine[i-2] ..