728x90 반응형 beakjoon5 [백준/python] 9205 - 맥주 마시면서 걸어가기 문제: https://www.acmicpc.net/problem/9205 사용 알고리즘: bfs 너비우선탐색 집에서 상근이는 맥주 20개를 가지고 출발50미터 갈 때마다 맥주를 1개씩 먹으면서 감편의점에서 살 수 있는 맥주의 최대 개수 20개 -> 집에서 출발해서 한번에 갈 수 있는 최대 거리: 50미터 * 20병 = 1000미터-> 편의점에서 맥주를 샀을 때 한번에 갈 수 있는 최대 거리: 50미터 * 20병 = 1000미터 1. 상근이의 현재 위치에서 최종 목적지인 락페스티벌의 위치가 1000미터 이내이면 도착 가능2. 상근이의 현재 위치에서 최종 목적지인 락페스티벌의 위치가 1000미터 보다 멀면 편의점을 들려야 함3. 편의점을 들리면 맥주를 사고, 상근이 위치를 업데이트 시킴4. 1 2 3 과.. 2024. 5. 20. [백준/python] 1463 - 1로 만들기(DP) 문제: https://www.acmicpc.net/problem/1463 사용 알고리즘: DP 할 수 있는 연산- 1 빼기- 2로 나누기- 3으로 나누기 나는 dp 문제를 풀 때 잘 모르겠으면 손으로 써가면서 규칙을 찾아 점화식을 쓰는 편인데 이번 문제도 쓰면서 풀다보니 규칙이 보였다. dp[1] = 0 -> 1 은 아무 연산을 하지 않아도 1 이기 때문에 연산 횟수는 0dp[2] = 1 -> 2 는 2-1 또는 2//2 를 해서 1 로 만들 수 있고 최소 연산 횟수는 1dp[3] = 1 -> 3 은 3//3 을 해서 1로 만들 수 있고 최소 연산 횟수는 1 dp[4]: 4 -> 2 -> 1dp[5]: 5 -> 4 -> 2 -> 1dp[6]: 6 -> 2 -> 1dp[7]: 7 -> 6 -> 2-> .. 2024. 5. 20. [백준/python] 2156 - 포도주 시식 문제: https://www.acmicpc.net/problem/2156 사용 알고리즘: DP n 개의 포도주를 처음부터 차례로 돌면서 먹을지 안 먹을지 결정 - i 번째 포도주를 먹지 않는다 -> dp[i-1]- i 번째 포도주를 먹는다i-1 번째 포도주를 먹는 경우 (직전 포도주를 먹는 경우) -> dp[i] = dp[i-3] + wine[i-1] + wine[i]i-2 번째 포도주를 먹는 경우 (전전 포도주를 먹는 경우) -> dp[i] = dp[i-2] + wine[i] 점화식: dp[i] = max(진전 포도주를 먹는 경우, 안먹는 경우, 전전 포도주를 먹는 경우) (i > 2) -> dp[i] = max(dp[i-3] + wine[i-1] + wine[i], dp[i-1], dp[i-2].. 2024. 5. 20. [Beakjoon/백준] 2579 파이썬 문제: https://www.acmicpc.net/problem/2579 사용 알고리즘: DP - 1번째 계단에 올라가는 법은 1가지 밖에 없음dp[1] = stairs[1] - 2번째 계단에 올라가는 법1번째 계단 -> 2번째 계단 : dp[2] = stairs[1] + stairs[2] -> 무조건 최댓값이 더 큼2번째 계단: dp[2] = stairs[2] - 3번째 계단에 올라가는 법1번째 계단 -> 3번째 계단: dp[3] = stairs[1] + stairs[3] 2번째 계단 -> 3번째 계단: dp[3] = stairs[2] + stairs[3]이 경우에는 계단에 부여된 점수에 따라 상황이 달라질 수 있음-> dp[3] = max(stairs[1] + stairs[3], stairs[2.. 2024. 5. 14. 이전 1 2 다음 728x90 반응형
