본문 바로가기
728x90

알고리즘316

[python] 백준 2437 저울 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 해결 추를 작은 것 부터 놓으면서 넘어가는 수를 찾아야한다. 처음에는 추를 안올려 놓으면 [0,0] 측정 가능하다는 것을 알음 1인 추를 올려 놓으면 [0,1] 측정 가능하다는 것을 알음 2인 추를 올릴려 할 때 현재 max값 1에서 현재 min값 0+2 까지 1칸 차이기 때문에 연속적이라는 것을 알음 따라서 2를 올려 놓으면 [0,3] 측정 가능하다라는 것을 알음 5인 추를 올려 놓으려 할 때 현재 .. 2023. 3. 11.
[python] 백준 16953 A->B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해결 전형적인 가장 쉬운 완전탐색 문제라 생각했다. bfs가 dfs보다 편할 것이라 생각했다. heapq, deque 어떤 것을 써도 상관 없다.(근데 deque가 속도가 더 빨랐다.) CODE from collections import deque import sys INF = sys.maxsize a, b = map(int, input().split()) ans = INF def bfs(): global ans que = deque() que.append((a,0)) while que: x, cnt = que.po.. 2023. 3. 11.
[python] 백준 1937 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 해결 계속해서 그래프 안을 상하좌우 움직이고 갔단 곳은 안가므로(숫자가 증가 수열이므로) DFS 사용하는 것이 좋을 것이다. 그런데 그냥 쓰면 당연히 시간초과가 날 것이다. 이전에 방문해서 결과를 냈던 것은 저장을 하는 것이 필요하다. 그러기 위해서는 dp를 사용해서 이전에 (r,c) 좌표에서 DFS 시작했을 때 최댓값이 dp[r][c] 였다.라고 저장되어있으면 넘어간다. CODE.. 2023. 3. 10.
[python] 백준 17070 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 해결 파이프는 그래프에서 0좌표에만 놓을 수 있다. (1은 벽이므로) 파이프를 놓는 방법의 수는 이전 장소 (r,c) 좌표면 (r-1,c), (r,c-1), (r-1,c-1) 좌표의 영향을 받는다. 각 좌표에 어떻게 놓느냐에 따라 경우의 수가 달라진다. 문제의 그림을 참고하는 것이 좋다. DP를 3차원을 이용해서 풀면 충분히 쉽게 풀 수 있다. CODE n = int.. 2023. 3. 9.
728x90