분류 전체보기154 [Python] 백준 13302번: 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 1. bfs+dp를 이용하여 접근하였다. 쿠폰은 최대 100 / 5 * 2 = 40개를 가질 수 있으므로 열을 40으로 잡았다. 2. 다음날이 가능하면 현재날+1, 현재 날 + 3일, 현재 날+ 5일로 각각 받을 수 있는 쿠폰의 개수 배열에 최솟값을 넣어준다. 3. 다음날이 불가능하면 다음날을 queue에 삽입하고 반복문을 탈출한다.(다음날이 불가능하면 티켓을 아에 살수가 없음) INF = 21470000.. 2021. 10. 18. [Python] 백준 2666번: 벽장문의 이동 https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 1. 첫번째 방법으로는 브루트포스로 문을 왼쪽으로 이동하는것과 오른쪽으로 이동한것을 모두 탐색하는것이다. 2. 아래는 dp로 푼것인데 현재문에서 선택할문의 거리를 더해주면서 최소값을 구하는 bottom-up 방식이다. n = int(input()) a, b = map(int, input().split()) m = int(input()) ans = 2147000000 flow = [-1] doo.. 2021. 10. 15. [Python] 백준 1351번: 무한 수열 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 0 ≤ N ≤ 10^12 2 ≤ P, Q ≤ 10^9 1. 범위가 위와같은데 시간제한은 2초이므로 일반 배열로 dp를 할경우 배열의 길이를 N만큼 잡아야하는데 이러면 시간초과가 난다. 2. n값을 p, q로 나눈 몫으로 top-down 방식으로 진행한다. 3. 메모이제이션은 배열이아닌 사전을 이용한다. 계속 트리형식으로 나누어 지기때문에 시간복잡도는 O(logN)으로 무난히 통과한다. n, p, q = map(int, input().split()) dic = {} dic[0] = 1 def go(k): i, j = k // p, k // .. 2021. 10. 15. [Python] 백준 2624번: 동전 바꿔주기 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 동전의 갯수가 정해져있기 때문에 이전행에 동전의 갯수(cnt) * 금액(val) 만큼 dp를 더해주면된다 점화식은 dp[i][j] = dp[i][j] + dp[i-1][j-v*val] ( 1 2021. 10. 15. 이전 1 ··· 24 25 26 27 28 29 30 ··· 39 다음