본문 바로가기
728x90

알고리즘316

[python] 백준 2573 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해결 빙산의 녹는 것을 계산한 다음 바다로 인해 하나였던 빙산이 두 개 이상으로 분리되는데 걸린 시간을 구하는 문제 bfs를 통해 빙산의 개수를 구할 수 있다. CODE import sys input = sys.stdin.readline from collections import deque def bfs(x,y): que = deque() que.append((x,y)) visited[.. 2023. 3. 26.
[python] 백준 9084 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 dp[i]는 i원을 만드는데 가지수를 나타내는 것이다. 1원부터 $10^{4}$까지 차례로 dp를 통해 나타낸다. 동전이 있는것은 1개로 되므로 dp[coin]은 1이상이다. CODE for _ in range(int(input())): n = int(input()) coins = list(map(int, input().split())) total = int(input(.. 2023. 3. 22.
[python] 백준 1092 배 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 해결 어떻게 배분해야할지 사고는 쉬웠다. 하지만 sort를 쓰고 이중 for문을 쓰는 것은 상당히 부담스러웠다. 하지만 방법이 생각이 안나 python3로 돌렸지만 시간초과 났다. pypy3로는 잘 풀렸다. 다른 풀이는 딱히 없는 것 같다. CODE import sys input = sys.stdin.readline n = int(input()) C = list(map(int.. 2023. 3. 21.
[python] 백준 1495 기타리스트 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 해결 전형적인 DP문제 dp[i][j]를 i번째 볼륨조절 후 j의 볼륨 가능 유무로 정의할 수 있다. CODE import sys input = sys.stdin.readline n, s, m = map(int, input().split()) # 곡 개수, 시작 볼륨, 최대 볼륨 V = [0] + list(map(int, input().split())) .. 2023. 3. 20.
728x90