DP

[python] 백준 - 9084. 동전

🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하여 만들 수 있으면 카운트를 세어준다. 4. 위의 표 처럼 각 동전을 꺼냈을 때 미리 만들어진 금액(인덱스)에 꺼낸 동전을 더해서 값을 쌓는다. 💨 다이나믹프로그래밍은 한번 해결한 문제는 다시 해결하지 않는다. 그리고 작은 문제를 해결하여 큰 문제를 해결한다는 의미!!!!!!!!! DP는 항상 어렵다.... 💻소스 코드 def _dp(): dp = [0] * (target + 1) # 경우의 수를 업데이트 할 리스트 dp[0] = 1 for coin in coins: # print('꺼낸 동전: ',c..

[python] 백준 - 1309. 동물원

🤔문제 해결 1. S1 | DP 2. 사자가 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우의 리스트를 만든다. 3. i번째에서 i-1번째에 사자의 상태에 따라 i번째의 경우의 수가 결정된다. (1) i번째에 사자가 없는 경우는 i-1번째에 사자가 왼쪽, 오른쪽 그리고 없어도 된다. (2) i번째에 사자가 왼쪽에 있는 경우는 i-1번째에 사자가 오른쪽에 있는 경우와 없는 경우만 가능하다. (i-1번째에 왼쪽에 있으면 i번째에서는 왼쪽에 있을 수 없다) (3) 오른쪽도 마찬가지 4. 경우의 수를 점차 더해나가면서 마지막 경우의 수를 다 더해준다. 💨 마지막에만 9901로 나누려고하면 메모리초과가 발생한다. 값을 쌓을 때 부터 나눠주면서 하자. 💻소스 코드 if __name__ == "__..

[python] 백준 - 1495. 기타리스트

🤔문제 해결 1. S1 | 다이나믹프로그래밍 2. 각각의 연주 차례에 가능한 볼륨을 저장하기 위해 2차원 리스트를 만든다. 3. 리스트를 설명하자면 맨 첫줄(i = 0)은 연주 시작전 단계이고 값이 0이 아니라 1인 부분은 내가 가지고 있는 볼륨이다. 현재 테스트케이스 예시(S=5)로 작성됐으므로 [0][5] = 1 이다. 4. 테스트케이스: 시작값 5, 최대값 10, 연주리스트 = [5, 3, 7] 5. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 현재 볼륨은 5, 첫번째 연주 볼륨은 5 이므로 5+5 = 10, 5-5 = 0 으로 둘다 0보다 크고 10보다 작으므로 아래와 같이 저장할 수 있다. 6. 첫번째 연주를 하기 전에 볼륨을 바꾼다. 첫번째와 다른점은 현재 볼륨이 2가지(0과 10)이다. 먼저 현..

[python] 백준 - 11660. 구간 합 구하기 5

🤔문제 해결 S1 | DP (0,0) 부터 리스트의 모든 지점까지 각각의 합을 구한다. 2번을 수행하고 나면 아래와 같은 결과를 얻을 수 있다. 합을 누적한 리스트로 아래 그림처럼 구하고자 하는 영역을 구하고 필요없는 부분은 빼주면 된다. 여기서 많이 헷갈릴 수 있는데 문제는 1,1부터 시작하지만 우리는 0,0부터 시작한다. 또, 빼줘야하는 영역(빨간색) 부분은 두번 빼는 경우가 있기 때문에 다시 더해줄 영역(초록색)을 한번 더해준다. 여기서 끝이 아니다. x축이 처음부터 인경우와 y축이 처음부터인 경우, 둘 다 아닌경우 이 3가지 경우로 나눠서 풀어줘야한다. 💨 시간초과 때문에 힘들었던 문제... 💻소스 코드 import sys from itertools import accumulate # 누적 합을 ..

[python] 백준 - 11048. 이동하기

🤔문제 해결 1. DP | silver1 2. 주어진 2차원 배열보다 한칸씩 더 큰 0으로 채워진 배열을 만든다. (한칸씩 더 많은 이유는 가장 윗줄과 가장 왼쪽줄도 비교해주기 위해서) 3. 현재 지점의 값(maze)과 그 점 이전의 값들(왼쪽, 왼쪽위, 위)중 큰 값(dp)을 더해서 (dp에) 값을 계속 쌓아 준다. 💨 다이나믹프로그래밍 문제. BFS로도 간단히 풀 수 있지만 시간초과가 난다. 💻소스 코드 N, M = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(N)] # 가장 윗줄과 가장 왼쪽줄도 비교를 해줘야 하기 때문에 한칸씩 더해서 만들어준다. dp = [[0] * (M + 1) for _ in ..

[python] SWEA - 3752. 가능한 시험 점수

문제 해결 1. D4 | DP 2. 얻을 수 있는 최대점수를 길이로 하는 리스트를 만든다 3. 리스트안의 값은 내가 점수를 얻을 수 있으면 1, 없으면 0으로 한다 4. 점수를 하나씩 받아서 리스트를 뒤에서부터 탐색한다 (1) 1을 만나면(내가 이미 얻을 수 있는 점수 ex. lst[3] == 1 이면 3점은 이미 얻을 수 있는 점수이다.) 내가 꺼낸 점수를 더해서 그 지점을 1로 만들어준다.(ex. score == 2 이면 lst[5] = 1) 5. 리스트에서 1의 갯수를 세어주면 정답. 💨 풀이 예시] 새로 받는 점수는 2, 3, 5이다. 얻을 수 있는 점수는 리스트는 lst = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 이렇게 구성한다. (0점은 처음부터 가능하므로 0번 인덱스의 ..