Algorithm Solving/Softeer
[소프티어] 지우는 소수를 좋아해 (파이썬)
bu119
2023. 8. 1. 09:00
728x90
반응형
난이도 : ★★★★☆
https://softeer.ai/practice/info.do?idx=1&eid=582
Softeer
연습문제를 담을 Set을 선택해주세요. 취소 확인
softeer.ai
📄 문제
- 여러 체육관을 거쳐 체육관 배지를 얻은 후 마지막 포켓몬 리그에서 사천왕과 챔피언에게 도전해야 하는 임무
- 각각의 체육관에는 체육관 관장들이 있고 그 관장들을 이겨야 체육관 배지를 얻을 수 있다.
- 관장들을 이기기 위해선 그 관장들이 갖고 있는 레벨(level)보다 높아야 한다.
- 체육관 관장들은 체육관 오는 길에 레벨 제한을 두었다. ‘X레벨 이하 지원자는 오지 마시오.’
- 지우는 자신이 포켓몬 리그에 나가기 위한 최소한의 레벨이 알고 싶어졌다.
- 지우는 자신의 레벨도 소수(Prime Number)에 맞춰서 포켓몬 리그에 참여하고 싶어 한다.
- 지우는 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다. ★
지우의 조건을 맞추어 지우에게 각각의 체육관을 넘어 마지막 장소인 포켓몬 리그에 참여할 수 있는 최소한의 레벨을 알려주는 프로그램을 작성해보자.
💡 아이디어
- A번 체육관과 B번 체육관 사이에 필요 레벨이 C인 길이 존재한다.
- a,b 사이에 값이 존재한다. (다익스트라 사용)
- 최소 레벨 경로를 찾는 함수가 필요하다.
- 각 체육관을 돌면서 필요 레벨의 최대 값이 최소가 되는 경로를 찾는다.
- 최소 레벨 경로 안에서 최대 레벨을 찾는다.
- 소수를 찾는 함수가 필요하다.
- 찾은 최대 레벨보다 큰, 가장 가까운 소수를 찾는다.
반응형
📝 문제 풀이 (Code)
import sys, heapq
# 소수 찾기
def is_prime_number(num):
for k in range(2, num):
if num % k == 0:
return False
return True
# 최소 경로 찾기
def dijkstra():
maxV = 1000000001
visited = [maxV] * (n + 1)
visited[0] = 0
# 레벨, 위치
heap = [(0, 1)]
visited[1] = 0
while heap:
level, curr = heapq.heappop(heap)
if curr == n:
continue
if visited[curr] < level:
continue
for posi, new_level in gym[curr]:
# 경로 중 최대 level을 업데이트
max_level = max(new_level, level)
if max_level < visited[posi]:
visited[posi] = max_level
heapq.heappush(heap, (max_level, posi))
return visited[n]
# ★ 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다.
# 1. 소수 찾는 함수
# 2. 레벨 체크 하는 함수
# 체육관의 개수를 나타내는 정수 N과 체육관 사이의 길의 개수 정수 M
n, m = map(int, input().split())
gym = [[] for _ in range(n + 1)]
# A번 체육관과 B번 체육관 사이에 필요 레벨이 C인 길이 존재한다. (a,b 사이에 값이 존재 - 다익스트라)
for _ in range(m):
a, b, c = map(int, input().split())
gym[a].append((b, c))
gym[b].append((a, c))
# 관장 최소 레벨 찾기
num = dijkstra()
# 관장들이 갖고 있는 레벨(level)보다 높아야 함
num += 1
# 소수 찾기
while not is_prime_number(num):
num += 1
print(num)
728x90
반응형