OSNIM

문제: https://www.acmicpc.net/problem/11660 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오. 입력 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, ..

문제: https://www.acmicpc.net/problem/11659 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 첫번째 제출 코드 (정답) import sys n, m = map(int, sys.stdin.readline().split()) arr = list(..

문제 : https://www.acmicpc.net/problem/2096 첫번째 제출 코드 (메모리 초과) import sys def solve(): MAX = 0 MIN = 0 for i in range(1, N): for j in range(3): if j == 0: dp[i][0] = arr[i][0] + max(dp[i-1][j], dp[i-1][j+1]) elif j == 1: dp[i][1] = arr[i][1] + max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) else: dp[i][2] = arr[i][2] + max(dp[i - 1][j], dp[i - 1][j - 1]) MAX = max(dp[-1]) for i in range(1, N): for j i..

문제 : https://www.acmicpc.net/problem/2293 정답 코드 import sys def solve(): for coin in arr: for j in range(coin, K+1): dp[j] += dp[j-coin] print(dp[K]) return if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) arr = [int(input()) for i in range(N)] # dp[1]는 1개만 골랐을 때 경우의 수 # dp[0]은 하나의 동전만으로 k원 만드는 경우의 수를 의미 = 1 dp = [1] + [0]*K solve() 결과 및 정리 전형적인 DP 문제 메모리가 4MB라..

문제 : https://www.acmicpc.net/problem/2038 골룽 수열은 1이 1개, 2가 2개 있으니 2번, f(3) = 2 이므로 3이 2번 나타나는 단조 증가하는 수열입니다. 수열을 숫자로 풀면 다음과 같습니다. [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8..] 첫번째 제출 (시간초과) import sys def solve(dp): left = 1 right = 0 k = 3 while len(dp) < n: dp = dp + [k]*(dp[left]) left += 1 k = k+1 print(dp[n-1]) return if __name__=="__main__": n = int(sys.stdin.read..

문제 : https://www.acmicpc.net/problem/2225 import sys def solve(): arr = [[0] *(N+1) for i in range(K+1)] for i in range(1, K+1): for j in range(1, N+1): if j == 1: arr[i][j] = i elif i == 1: arr[i][j] = 1 else: arr[i][j] = arr[i-1][j] + arr[i][j-1] return arr[K][N] if __name__ == "__main__": input = sys.stdin.readline N, K = map(int, input().split()) print(solve()%1000000000) arr의 행은 K(정수의 개수)를 ..

문제 : https://www.acmicpc.net/problem/12865 정답 코드 import sys def knapsack(N, capacity): for i in range(1, N+1): W = weight[i-1] V = value[i-1] for j in range(1, capacity+1): if W > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(V+dp[i-1][j-W], dp[i-1][j]) return dp[N][capacity] if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) #행은 아이템의 개수 #열은 가방의 최대 무대 #dp[i][j] ..

문제 : https://www.acmicpc.net/problem/2011 제출 코드 def solve(): code = list(map(int, input())) dp = [0] * (len(code)+1) dp[0] = 1 dp[1] = 1 if code[0] == 0: print(0) return N = len(code) code = [0] + code for i in range(2, N+1): one = code[i] if one > 0: dp[i] += dp[i-1] two = code[i-1]*10 + code[i] if 10

문제 : https://www.acmicpc.net/problem/2133 풀이 N 일때 dp[N]의 위 그림 오른쪽처럼 3개로 나누어 집니다. 1. dp[N] = dp[N-2] x 3 2. dp[N] += i는 2부터 N-4 까지 dp 값에 2를 곱하고 모두 더한 부분 3. N이 2씩 증가할 때 마다 나타나는 새로운 타일 배열 : +2 제출 코드 def solve(): n = int(input()) dp = [0] * (30+1) dp[1] = 0 dp[2] = 3 for i in range(4, n+1): if i%2 == 1: continue dp[i] = dp[i-2]*3 for j in range(0, i-2, 2): dp[i] += dp[j]*2 dp[i] += 2 print(dp[n]) re..

문제 : https://www.acmicpc.net/problem/2579 첫번째 풀이 (재귀, 시간초과) start: 시작 인덱스, seq: 연속 2개 선택하는 것 판단 result: 현재까지 선택한 계단의 합 def dfs(start, seq, result): global ans if seq > 2: return if start > N: return if start == 5: ans = max(ans, result) return if start + 1 < N: dfs(start + 1, seq+1, result+a[start+1]) if start + 2 < N: dfs(start + 2, 1, result+a[start+2]) N = int(input()) a = [] ans = 0 for i in..