https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def dfs(): if len(s) == m: print(' '.join(map(str, s))) return for i in range(1, n+1): if visited[i]: continue visited[i] = True s.append(i) dfs() s.pop() visited[i] = False n, m = map(int, input().split()) s = [] visited ..

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net # 21317번 징검다리 건너기 # DP ''' 접근 방법: DP1[N] = N번째까지 도착했을 때, 매우 큰 점프 없이 산삼을 얻기 위해 필요한 에너지 최솟값 DP2 -> [] 계속 append 1번째돌에서 슈퍼점프한 후 ~~ 두번째 돌에서 슈퍼점프 한 후 ~~ 세번째 돌에서 슈퍼점프 한 후 ~~ k번째 돌에서 슈퍼점프 한다면 DP2 = DP1.copy DP2[k+3] = DP1[k] + very_big_jump DP2를 DP1만든것처럼 계속 갱신해줘(k+4)부터 DP2[N] ~~N-3번째 돌에서 슈퍼점프 한 후~~ ''..

import sys input = sys.stdin.readline n, m = map(int, input().split()) data = [list(map(int, input().split())) for _ in range(n)] sum_data = [[0] * (n+1) for i in range(n+1)] for i in range(1, n+1): for j in range(1, n+1): sum_data[i][j] = sum_data[i][j-1] + sum_data[i-1][j] - sum_data[i-1][j-1] + data[i-1][j-1] for _ in range(m): x1, y1, x2, y2 = map(int, input().split()) print(sum_data[x2][y2]..

문제풀이 백준 2579 계단오르기 문제와 상당히 유사하다. 차이점은 계단오르기는 마지막 계단을 꼭 밟고 끝나지만, 이 문제는 마지막 잔을 마시지 않을 수도 있다는 것이다. d[i]는 i번째 포도주까지 최대로 마신 포도주의 양이다.(0부터) i번째 포도주를 마시고 i-2번째까지 마신 양, i,i-1번째를 포도주를 마시고 i-3번째까지 마신 양, 그리고 i번째를 마시지 않는 경우(i-1번째 포도주까지 마신 양)를 모두 고려해야한다. 따라서 결과리스트는 [6, 16, 23, 28, 33, 32..]가 아니라 [6, 16, 23, 28, 33, 33..]이어야 한다. n=int(input()) wine = [0] * 10000 for i in range(n): wine[i] = (int(input())) d=[..

N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % 1000000000) 풀이 0을 제외한 모든 숫자는 앞에 올 수 있다. 이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1). 하지만 9 뒤엔 오직 숫자 8만이 올 수 있다. 이를 그림으로 표현하면 다음과 같다. dp테이블은 이차원..

import sys input = sys.stdin.readline A = [""] + list(input().rstrip()) B = [""] + list(input().rstrip()) LCS = [[""]*len(B) for _ in range(len(A))] # LCS[i][j]는 A의 i번째까지의 문자열과 # B의 j번째까지의 문자열의 LCS 길이 값을 의미함 # LCS[i][j]에서, 만약 A[i] == B[j]라면 # 그 두 문자를 제외한 i-1개, j-1개의 LCS # 만약 다르다면, i-1개, j개와 i개, j-1개 # 일 때의 LCS 중 큰 값 취하기. i-1개, j-1개 # 는 어차피 저 두 케이스보다 반드시 작거나 같으므로 # 두 케이스만 고려. # 그런데 LCS 리스트 원소 값이 ..