위상 정렬5 백준 2623번 : 음악프로그램 (Java) 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 구현 방법 출연 순서가 정해져 앞 가수가 먼저 출연해야 다음 가수가 출연할 수 있으므로 위상 정렬 알고리즘을 사용했습니다. 입력이 여러 가지로 나뉘어 들어오지만 결국 하나의 그래프임을 알 수 있습니다. 각 보조 PD가 담당하는 순서 관계를 전부 저장한 뒤 위상 정렬을 돌리면 끝~.~ 위상 정렬을 단계별로 나열하면 1. 가수들의 진입 차수를 확인하여 0인 가수만 큐에 삽입 .. 2022. 2. 21. 백준 1005번 : ACM Craft (Java) 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 구현 방법 건물 W를 건설하려면 건설 순서 규칙에 의해 규칙을 만족하는 건물들을 지어야 하므로 위상 정렬을 사용했습니다. 하지만 효율성이 그렇게 좋게 나오지 않아 그냥 이렇게 풀었구나~ 라고 참고만 하면 좋을 것 같습니다~~ 건설 시간을 저장할 수 있는 배열을 선언하여 하나 지을 때마다 다음 지을 수 있는 건설을 가져와 걸리는 시간을 저장해줍니다. 최소 시간이지만 앞서 지을 건물이 모두.. 2022. 2. 19. 백준 3665번 : 최종 순위 (Java) 문제 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 구현 방법 문제를 이해하는 데 시간이 넘나 오래 걸렸습니다.... 🤯 "예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다" 이 문장 때문에 너~~무 헷갈렸는데요. 아직도 정확하게 이해를 했는지.. 모르겠지만 일단 제가 이해한바로는 상대적인 순위가 더 높아질 수도, 더 낮아질 수도 있다 입니다. 따라서 .. 2022. 2. 16. 백준 14676번 : 영우는 사기꾼? (Java) 문제 https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 구현 방법 건물들이 이전에 반드시 건설된 상태여야 지을 수 있으므로 위상 정렬 알고리즘을 사용했습니다. 문제 풀이 과정을 간략하게 적자면 1. 건물 생성 시 진입 차수가 0이 아니거나 건물 파괴 시 건물 개수가 없으면 치트키를 사용하여 건물을 건설 or 치트키를 사용하여 건설한 건물을 파괴 하는 것이므로 치트키 사용을 알 수 있음 2. 건물 생성 시, 건물 개.. 2022. 2. 15. 이전 1 2 다음
