728x90 백준 풀이103 [백준/BOJ] - 9461번 python 풀이 - DP Key Point 1. 규칙은 다음과 같다. idx 5부터 본인 idx 기준 -5 위치에 있는 값을 더해주어 다음 값을 정하는 로직. 2. n의 최댓값이 100이라 했으므로 그냥 100까지 dp 배열을 한번에 만들고 출력하라는 값을 출력해주면 된다. import sys input = sys.stdin.readline n = int(input()) dp = [0] * 100 dp[0] =1 dp[1] =1 dp[2] =1 dp[3] =2 dp[4] =2 ex = [] for _ in range(n): ex.append(int(input().rstrip())) for i in range(5,100): dp[i] += (dp[i-1] + dp[i-5]) for item in ex: print(dp[item-1]) 2023. 1. 4. [백준/BOJ] - 1932번 python 풀이 - DP 1.Key Point 경우의 수가 3가지로 나누어지는 문제이다. 1번째 case는 가장 좌측 case - 가장 좌측 case는 좌측 배열의 값끼리 더해주면 된다. 2번째 case는 가장 우측 case - 가장 우측 case는 우측 배열의 값끼리 더해주면 된다. 마지막 case는 이외의 경우이다. - 바로 위(상위 행) 왼쪽이나 바로 위(상위 행) 중 max 값을 골라 본인 값과 더하는 과정을 거친다. import sys input = sys.stdin.readline n = int(input()) dp = [list(map(int, input().split())) for _ in range(n)] for i in range(1,n): #idx 1~4까지 idx 0은 값이 안 바뀌니까 무시 for j in.. 2023. 1. 4. [백준/BOJ] - 2156번 python 풀이 - DP Key Point 점화식을 구하기 위해 모든 경우의 수를 따져보면 다음과 같이 3가지 case로 나눠지는 것을 확인 할 수 있다. 노란색 하이라이트 부분이 기준이다. 가장 중요한 점은 dp기준으로 바로 다음 포도주를 먹을 수 있다는 확신이 없다는 점이다. 왜냐하면 dp 기준 바로 이전 포도주를 마셨을 경우 2번 연속 마셨다는 가정이 되는데, 바로 다음 포도주를 마셔버리면 조건에 위배되기 때문이다. 2579 계단 문제와 다른 점은 마지막 계단을 꼭 밟아야 한다는 조건 때문에 dp를 계산할 때 해당 idx의 계단을 밟는다고 가정하고 값을 구해야한다. 반면 해당 문제는 해당 조건이 없으므로 바로 직전 포도주의 dp값을 그대로 넘겨받아도 문제가 없는 것이다. 그렇기에 점화식에 차이가 발생한다. https://w.. 2022. 12. 29. [백준/BOJ] - 1912번 python 풀이 - DP Key Point 1. 일반적인 dp문제와 같이 규칙을 찾아 점화식으로 나타내면 되는 문제이다. 2. 이 문제는 본인 값 & 이전 값 dp랑 본인값 합한 값 중 max를 dp에 갱신하면 되는 문제이다. 3. 각 dp에는 해당 수까지의 최대의 값이 저장 되어 있다. 시간 초과 import sys mini = -sys.maxsize input = sys.stdin.readline n = int(input()) num = list(map(int, input().split())) dp = [mini] * 100000 for i in range(n): #8 sum = num[i] for j in range(i-1,-1,-1): #0 sum += num[j] dp[i] = max(sum,dp[i]) print(ma.. 2022. 12. 29. [백준/BOJ] - 11503번 python 풀이 - DP Key Point 1. dp를 사용하는 문제인데, dp 배열에 수열의 순서의 최댓값에 해당하는 값을 적는 알고리즘을 적용. 2. 모든 dp는 1로 초기화하고 위 예시를 기준으로 보면 10은 첫번째 수이므로 1 두번째 수 20은 앞서 있는 값보다 크기 때문에 dp 값 + 1 하여 2 세번째 수 10은 앞서있는 값 10, 20보다 크지 않으므로 dp값 변동 x (1) 네번째 수 30은 앞서있는 값 10, 20, 10보다 각각 크다. 각 case 마다 dp[idx]의 값+1과 네번째수 담당 dp 부분과 비교하여 큰 값을 해당 dp에 저장한다. 이런 방식으로 진행하면 수열의 길이의 최댓값이 저장 될 것이다. import sys input = sys.stdin.readline n = int(input()) d =.. 2022. 12. 29. [백준/BOJ] - 2579번 python 풀이 - DP Key Point dp 문제를 보면 일단 dp 배열의 값에 어떤 값이 들어갈지 이에 대한 규칙을 찾아야 한다. 보통 1,2 와 같은 앞에 있는 번호들은 점화식에 적용되지 않는 경우가 많으므로 인지하고 진행. d[0] = s[0] d[1] = s[0] + s[1] d[2] = max(s[0] + s[2], s[1] + s[2]) d[3] = max(d[0] + s[2] + s[3], d[1] + s[3]) # 2전 칸에서 1칸 이동 + 1칸 이동하여 해당 계단에 오는 경우도 있을 것이고 # 3전 칸에서 2칸 이동 + 1칸 이동하여 해당 계단에 오는 경우도 있다. 이 경우 중에 max값 도출. 2156 포도주 문제와 다른 점은 해당 문제는 마지막 계단을 꼭 밟아야 한다는 조건 때문에 dp를 계산할 때 해당 .. 2022. 12. 29. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음 728x90
