본문 바로가기
728x90

자료구조22

[python] 백준 2295 세 수의 합 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 해결 A[x]+A[y]+A[z] = A[k]를 보고 3개를 잡으려 하지말고 A[x]+A[y] =c= A[k]-A[z]로 바꿔서 생각해보려 하자. A[x]+A[y]=c로 가능한 c를 sample 집합에 넣는다. k를 가장 큰 n-1인덱스부터 0까지 차례로 고정시키면서 z를 0부터 k인덱스까지 보면서 A[k]-A[z] in sample을 확인하면서.. 2023. 4. 23.
[python] 백준 16562 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 해결 결국 친구 사이클(network)를 만들어서 거기서 친구비 가장 작은 값을 더해주는 문제. 즉 사이클과 그 사이클 안의 가장 작은 친구비를 구하면 된다. CODE import sys input = sys.stdin.readline INF = sys.maxsize sys.setrecursionlimit(10**6) def.. 2023. 4. 13.
[python] 백준 5052 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 해결 최대한 비교를 적게 하기 위해 문자열을 올림차순으로 정렬해서 이전 것이 다음 원소 안에 포함되는 것이 있는지 확인하면 된다는 것을 쉽게 알 수 있다. CODE t = int(input()) for _ in range(t): n = int(input()) result = [] for i in range(n): x = str(input().rstrip()) resul.. 2023. 4. 9.
[python] 백준 1781 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 해결 데드라인을 생각하면서 컵라면 수가 큰 것을 스택 안에 넣는 문제 스택 안의 원소의 개수를 데드라인이라고 생각하면 된다. 그러면 스택 안에 원소를 데드라인이 빠른 것부터 처리를 하며 만약 컵라면은 많이가져갈 수 있는데 데드라인이 걸리면 그 전에 작은 컵라면수를 빼고 넣으면 된다. CODE import heapq n = int(input()) table = [] for _ in range(n): d.. 2023. 4. 5.
728x90