DP

[python] 백준 - 9658. 돌 게임4

🤔문제 해결 S1 | 다이나믹 프로그래밍 이게임은 거의 선빵필승 구조이다. 특별한 경우만 빼고! 먼저 손쉽게 1~4개일 때의 경우를 구할 수 있다. 돌 1개: 선 - 후공 승 돌 2개: 선, 후 - 선공 승 돌 3개: 선, 후, 선 - 후공 승 돌 4개: 선선선, 후 - 선공 승 다음 5개부터는 점화식으로 구해보자. 돌이 5개일 때 상영이가 돌을 둘 수 있는 경우의 수는 1개, 3개, 4개이다 - 3가지 경우 먼저 상영이가 돌을 1개 뒀다고 하자 그럼 남은 돌은 4개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 4개에서는 선공이 무조건 이긴다. - 창근 승 다음 상영이가 돌을 3개 뒀다고 하자 남은 돌은 2개이고 창근이는 선공이 된다. 위의 4가지 경우를 봤을 때 돌 2개에서는 선공이 무조..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 단어 퍼즐(2017 팁스타운)

🤔문제 해결 Lv4 | 다이나믹 프로그래밍 풀이 방법은 앞에서 부터 문자 하나하나 선택한다. 'b', 'a', 'n', ... 그 문자로 끝나는 단어가 strs에 들어있는지 확인한다. 있으면 현재까지 썼던 단어 개수(dp[i])와 그 문자를 사용했을 때의 단어 개수를 비교해서 최솟값으로 갱신 (말이 너무 어렵다...) ["ba", "na", "n", "a"] 와 "banana"로 테스트 해보면 맨처음 "b"로 끝나는 단어는 없으므로 pass 다음 "a"로 끝나는 단어는 "a"와 "ba"가 있다. - "na"는 조건에 맞지 않음 "a"를 선택했을 때는 아무일도 없다. why? 처음에 b로 끝나는 단어가 없어서 값이 무한대인 상태 "ba"를 선택하면 1로 갱신해준다. - (단어 하나만으로 "ba"를 만들었다..

[python] 프로그래머스 - 도둑질

🤔문제 해결 Lv4 | DP "인접한 집은 털 수 없다" 까지는 크게 어려운 문제가 아니지만 "마을이 원형으로 되어 있다" 에서 한번 더 생각하게 하는 문제!! -> 0번째 집을 터는 경우( 마지막 집을 털지 못한다 )와 0번째 집을 안터는 경우 두가지로 나눌 수 있다. 먼저 0번집을 털 경우! 0번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 0번집을 턴다. dp[0] = money[0] 1번집에 들렀을 때 가장 많은 돈을 가져오는 경우는 1번집을 터는 경우지만 우리는 1번집을 반드시 털었다고 가정했으므로 인접한 2번집은 털 수 없다. dp[1] = 0 2번집에 들렀을 때: 인접한 1번집이 아닌 0번집 또는 -1번집(2번일 때는 없다) 중 돈을 많이 가져왔던 집에서 온다. dp[2] = money[i..

[python] 백준 - 11052. 카드 구매하기 / 16194. 카드 구매하기 2

🤔문제 해결 S1 | 다이나믹 프로그래밍 dp 리스트를 만든다. dp[i]: 카드 i장을 구매하기 위한 지불 금액의 최솟값 dp[0] = float('inf') (파이썬에서의 최댓값) dp[i-j] + dp[j]: 카드를 j장 구매하기 위한 최솟값과 카드를 i-j장 구매하기 위한 최솟값의 합 ex) dp[2] + dp[3]: 카드를 2장 구매하고 3장구매할 때의 최솟값 dp[i-j] + dp[j] 와 dp[i] 의 값을 비교하여 더 작은 값을 dp에 저장 테스트케이스 1번 예시 dp[0] = float('inf') dp[1] = 1 dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2 dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1..

[python] 백준 - 2240. 자두나무

🤔문제 해결 S1 | 다이나믹프로그래밍 1. 답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다. 다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다. 하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다. 홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다. 2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다. dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때 3. %중요% (1) 받아 먹는 조건: a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면 b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 ..