본문 바로가기
728x90

전체 글423

[python] 백준 2643 색종이 올려 놓기 https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 문제 해결 작은 것부터 쌓아 올려서 최대한 많이 쌓을 수 있도록 하면 된다. w, h가 구별되지 않으므로 두 변중 긴 변을 w, 작은 변을 h로 정렬한다. 각 색종이를 길이가 큰 것 부터 내림차순으로 정렬한다 하나씩 확인하면서 이전 것들 길이를 비교하면서 w, h 모두 더 길 때 dp[w][h] (가장 큰 색종이의 길이가 w, h일 때 쌓아올릴 수 있는 최대 개수) 를 dp[pw][.. 2024. 4. 8.
[python] 백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 문제 해결 플로이드-위셜 방법을 써야한다는 것은 쉽게 알 수 있었다. 하지만 어떻게 끊는 것을 구현할 지 생각이 나지 않았는데 check를 통해서 끊게 된다면 check[i][j]=0을 통해 이를 저장할 수 있었다. CODE import sys input = sys.stdin.readline def main(): result = 0 for k in range(n): for i in range(.. 2024. 4. 6.
[python] 백준 2436 공약수 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 문제 해결 최소 공배수를 최대 공약수로 나누었을 때의 수를 서로소인 두 인수로 쪼개서 확인하는 작업을 하면 끝 CODE import sys input = sys.stdin.readline import math def solve(res,a): target = sys.maxsize x, y = -1, -1 for i in range(1,int(math.sqrt(res)+1)): if res%i:con.. 2024. 4. 4.
[python] 백준 11562 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해결 graph[u][v] : u에서 v까지 가는데 필요한 양방향화 필요한 길 개수 처음에 INF로 정의한다음 연결되어있다고 입력값이 주어지만 graph[u][v] = 0 만약 양방향이 아니고 u→v는 연결이 되어있는데 v→u는 연결이 안되어있으면 graph[v][u] = 1로 정의 플로이드-위셜을 이용하여 필요한 양방향화 길의 개수를 구할 수 있다. 플로이드-위셜로 최소거리가 아닌 필요한.. 2024. 4. 3.
728x90