알고리즘53 Python - 아기 상어 (16236) BFS, 우선순위 큐 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 우선순위 큐가 비어있다면 break 2. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 3. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 4. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마.. 2023. 8. 15. Python - 포도주 시식 (2156) DP https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. cnt가 3 이상이라면 1) [ i ] 와인 + [ i - 1 ] 와인 + DP[ i - 3 ] 2) [ i ] 와인 + DP[ i - 2 ] * 3) DP[ i - 1 ] 위 세 가지 경우의 수 중 가장 큰 값을 DP 배열에 저장합니다. 3번을 고려해야 하는 이유 현재 와인에서 2가지 방법으로 와인을 마시는 것보다 바로 이전 기록해놓은 양이 더 많으면 이전 기록을 중복 저장합니다. impor.. 2023. 8. 13. Python - A -> B (16953) 그리디, 재귀 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 1. 재귀 - 이진 트리 모양으로 뻗어 나가면서 모든 경우를 해보는 방법 2. 그리디 - 만들어야 하는 수를 원래 수로 만드는 방향 - 1순위 : 10으로 나누었을 때 1이 남으면 10으로 나눔 - 2순위 : 2로 나누어 떨어지면 2로 나눔 - 나누어 떨어지지 않거나 원래 수보다 작아지면 답은 -1 재귀 코드 import sys input = sys.stdin.readline n, m = map(int, input().strip().split()) ans = -2 def pro(x, y, d): global ans if .. 2023. 8. 13. Python - 다리 만들기 (2146) BFS https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net - 큐에 넣는 경우의 수 1) 다리가 만들어지지 않았다면 큐에 저장 1. 섬이 모두 1로 입력을 받으니 따로 섬을 구분하고 섬의 위치를 큐에 저장합니다. 2. 각 섬에서 모든 방향으로 다리를 놓습니다. 3. 다른 섬에서부터 만든 다리를 만난다면 정답을 저장합니다. (최솟값으로) 갔던 곳은 다시 되돌아가지 않으므로 시간복잡도는 O(n2) import sys from collections import de.. 2023. 8. 12. Python - 사다리 조작 (15684) 브루트포스, 백트래킹 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. arr[x][y - 1] + arr[x][y] + arr[x][y + 1] 코드를 통해 가로줄을 놓을 위치와 양 옆의 합이 0보다 크면 중복으로 놓거나 연속으로 놓는 경우이므로 continue 합니다. import sys input = sys.stdin.readline n, m, h = map(int, input().strip().split()) arr = [[0 for i in range.. 2023. 8. 2. Python - 토마토 (7569) BFS, 3차원 배열 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 3차원 배열은 [z 번째 2차원 배열][x 행][y 열]로 좌표값만 미리 잘 정해놓으면 일반적인 BFS와 거의 똑같았습니다. import sys from collections import deque input = sys.stdin.readline m, n, h = map(int, input().strip().split()) allSum = m * n * h ans = 0 q.. 2023. 8. 1. 이전 1 2 3 4 ··· 9 다음
