알고리즘60 [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. [Python] 백준 2602번: 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 키값을 기준으로 돌다리를 체크한다. 2. 현재 돌다리가 천사면 악마 악마면 천사로 이전 키값을 기준으로 배열을 뒤에서 부터 탐색한다. 3. 전의 키값의 dp가 저장되어있으면 모든 dp의 값을 더해주고 없으면 경로가 존재하지 않으므로 0으로 초기화한다. (배열을 뒤에서 탐색하는이유 앞에서부터 탐색하면 경로가 0이되어 뒤에 존재하는 경로도 0이 되기때문) 4. 마지막 키값에 도달했을때 총합을 더해준다. k.. 2021. 10. 14. 이전 1 2 3 4 5 6 7 ··· 15 다음