DP 문제https://www.acmicpc.net/problem/2293💡 풀이코드 (실패 - 메모리 초과)import sys n, k = map(int, sys.stdin.readline().split())coin = [0] for _ in range(n): num = int(sys.stdin.readline()) coin.append(num) def sol(n, k, coin): dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = 1 for i in range(1, n + 1): for j in range(1, k + 1..

DP 문제 https://www.acmicpc.net/problem/15989접근 방식1, 2, 3 더하기 문제와 다른점1, 2, 3 더하기 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 순열 문제이다.아래 두가지 경우는 각각 다른 경우이다.1+2+12+1+11, 2, 3 더하기 4 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다.아래 두가지 경우는 같은 경우이다.1+2+12+1+1동전 문제와 같은점동전 문제는 주어진 동전의 금액을 활용하여, 그 금액의 합이 k원이 되도록 만드는 조합 문제이다.이 문제는 1, 2, 3을 활용하여, 그 합이 k가 되도록 만드는 조합 문제이다.따라서, 동전 문제와 같은 방법으로 문제를 풀 수 있다.💡 풀이코드 (성공 - 2차원 ..

DP 문제https://www.acmicpc.net/problem/9095💡 풀이코드 (성공 1)import sys t = int(sys.stdin.readline())def dynamic(n): dp = [0 for _ in range(n + 1)] dp[0] = 1 dp[1] = 1 dp[2] = 2 dp[3] = 4 for i in range(4, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] print(dp[n])for _ in range(t): n = int(sys.stdin.readline()) if n == 0: print(1) elif n == 1: p..

DP 문제https://www.acmicpc.net/problem/17404문제 요약1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.💡 풀이 코드 (실패 - 마지막 행을 0번째 행으로 옮겨 겹치지 않게 하는 코드)'''51 10 1001 10 1001 10 1001 10 1001 10 100출략 : 32정답 :122'''# 마지막 행을 0번째 행으로 옮겨 겹치지 않도록 하자.import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ ..

DP 문제https://www.acmicpc.net/problem/1149 💡 풀이 코드 (성공)import sys n = int(sys.stdin.readline())graph = [[0] * 3 for _ in range(n + 1)]dp = [[0] * 3 for _ in range(n + 1)]for i in range(1, n + 1): graph[i][0], graph[i][1], graph[i][2] = map(int, sys.stdin.readline().split()) if i == 1: dp[i][0],dp[i][1],dp[i][2] = graph[i][0],graph[i][1],graph[i][2]def sol(n, graph): for i in ..

누적합, 수학 문제https://www.acmicpc.net/problem/10986접근 방식이 문제는 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수(부분구간의 개수)를 구하는 것이다.부분구간의 개수를 구해야 하므로 투포인터 알고리즘을 잠깐 떠올렸으나 주어진 데이터의 앞뒤 연관성이 없기 때문에 다른 방법을 고안해냈다. 투포인터 알고리즘을 쓸 수 없는 이유1) 투포인터 알고리즘의 일반적인 사용 사례투포인터 알고리즘은 주로 다음과 같은 조건을 만족하는 경우에 사용된다.정렬된 배열: 배열이 정렬된 상태에서 특정 합을 찾는 문제.특정 조건을 만족하는 구간: 예를 들어, 구간의 길이 또는 합이 특정 조건을 만족하는 경우.단일 스캔: 한 번의 배열 스캔으로 문제를 해결할 수 있는 경우.2) 투포인터 ..