본문 바로가기

ALGORITHM/백준67

[BOJ/PYTHON] 15889. 호 안에 수류탄이야!! 백준 문제 링크: https://www.acmicpc.net/problem/15889 문제 요약 수류탄을 마지막 사람까지 무사히 전달해야 각자 팔힘에 따라 사거리가 다름. 사거리 내의 누구에게나 수류탄 전달 가능. 사거리가 짧아 다음 전우에게 전달되지 못하면 영창 생활 시작 게임이 무사히 마무리될 수 있을지 구하기 핵심 아이디어 다음 사람까지의 거리보다 사거리가 짧으면 실패한다고 보면 된다. "사거리 내의 누구에게나" 전달 가능하기 때문에 바로 다음 사람한테 전달하지 않아도 되고, 건너뛸 수도 있다. 현재 사람의 좌표에 사거리를 더한 거리가 다음 사람의 좌표보다 작으면 실패한다고 보면 된다. 풀이 # silver4-15889. 호 안에 수류탄이야!! import sys input = sys.stdin.r.. 2023. 5. 25.
[BOJ/PYTHON] 9009. 피보나치 백준 문제 링크: https://www.acmicpc.net/problem/9009 문제 요약 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수 구하기 핵심 아이디어 및 풀이 피보나치 리스트를 먼저 구하고 시작하면 된다. 이때, 입력이 최대 1,000,000,000이기에 피보나치를 50번째까지 구해줬다. (사실 50번째까지 안 가도 되는데 0으로 딱 끝내려고 이렇게 했다) 최소 개수가 되려면 그리디하게 제일 큰 값부터 넣어보면 되기에 피보나치 리스트를 큰 값부터 내림차순으로 정렬한다. 피보나치 리스트를 순서대로 돌면서 입력값보다 피보나치가 딱 작아지는 순간부터를 answer list에 append해줬다. 그리고 append한 수만큼을 입력값에서 빼 다음 피보나치를 구하면 .. 2023. 5. 25.
[BOJ/PYTHON] 2437. 저울 백준 문제 링크: https://www.acmicpc.net/problem/2437 문제 요약 추를 사용해 측정할 수 없는 양의 정수 무게 중 최솟값 핵심 아이디어 1 2 3로 만들 수 있는 것: 1 2 3 4 5 6 -> 측정 불가한 최소 7. 1 1 2 6로 만들 수 있는 것: 1 2 3 4 6 7 8 9 10 -> 측정 불가한 최소 5. 1 1 2 6의 케이스에서는 1 1 2로 만들 수 있는 최대 무게인 4 다음에는 1 더한 5를 만들 수 있어야 한다. 그런데 다음 추는 5보다 큰 6이 와서 연속성이 깨졌기에, 5를 ‘측정 불가한 최솟값’으로 판단하면 된다. 풀이 # gold2-2437. 저울 import sys input = sys.stdin.readline n = int(input()) # 저울.. 2023. 5. 25.
[BOJ/PYTHON] 2003. 수들의 합 2 백준 문제 링크: https://www.acmicpc.net/problem/2003 문제 요약 수열의 합이 M이 되는 경우의 수 핵심 아이디어 for문으로 수열을 돌면서 합을 구하는데, 합이 m이 되면 카운트를 올리면 된다. 풀이 # silver4-2003. 수들의 합 2 import sys input = sys.stdin.readline n, m = map(int, input().split()) array = list(map(int, input().split())) cnt = 0 # 합이 m이 되는 경우의 수 for i in range(n): # 수 하나만으로 m 만족하는 경우 if array[i] == m: cnt += 1 # 합으로 m 만족하는 경우 temp_sum = array[i] for j i.. 2023. 5. 25.
[BOJ/PYTHON] 13904. 과제 백준 문제 링크: https://www.acmicpc.net/problem/13904 문제 요약 과제 마감일 지켜야 점수 받을 수 있음. 얻을 수 있는 점수 최대값 핵심 아이디어 과제는 원래 발등에 불 떨어질 때 해야 하는 것 과제를 하루에 하나씩 처리한다. 기한 당일에 해당 과제를 한다고 간주하면 되는데, 그래야 앞에 기한 더 짧은 다른 과제를 할 수가 있다. 기한(마감일) 기준으로 정렬 후 for문을 돌아가며 점수를 하나씩 append해주면 된다. 점수 리스트에 들어간 점수의 개수는 처리해야 할 과제의 개수이다. 리스트의 점수의 개수가 마감일보다 크면 기한 안에 모든 것을 처리할 수 없기에 점수가 제일 작은 것을 버려주면 된다. heapq로 풀었는데, heapq에서 pop을 하면 점수가 제일 작은 것.. 2023. 5. 24.
[BOJ/PYTHON] 16562. 친구비 백준 문제 링크: https://www.acmicpc.net/problem/16562 문제 요약 친구비를 주면 한 달간 친구가 생긴다! '친구의 친구는 친구다'를 이용해 모든 사람과 친구가 되는 최소 비용 출력, 안 되면 Oh no 출력 핵심 아이디어 ‘친구의 친구는 친구’이기에 트리 계층 관계를 떠올릴 수 있고, ‘모든 사람과 친구’가 되어야 하기에 모든 노드를 연결한다고 생각하면 된다. union & find를 통해 친구 관계를 합쳐주는데, 비용 적은 애를 부모 노드로 해서 합쳐주고, 그 비용을 더하면 된다. 풀이 # gold4-16562. 친구비 import sys input = sys.stdin.readline n, m, k = map(int, input().split()) # 학생 수, 친구관계.. 2023. 5. 24.

티스토리툴바