본문 바로가기

전체 글108

백준 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.
백준 1938번 : 통나무 옮기기 (Java) 문제 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 구현 방법 중심을 기준으로 너비 우선 탐색을 해주었습니다. 가로일 때, 세로일 때로 구분되기 때문에 기본 동작을 할 때와 방문처리를 할 때 가로인지 세로인지 구분하여 구현했습니다. (1) U, D, L, R - 가로 일 때는 c-1, c, c+1 탐색 - 세로 일 때는 r-1, r, r+1 탐색 (2) T 회전일 때는 중심을 기준으로 8방을 탐색 이미 한 줄씩 계산하는.. 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.
백준 17244번 : 아맞다우산 (Java) 문제 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 구현 방법 비트마스킹을 사용하여 시간을 좀 더 줄일 수 있었겠지만 따로 비트마스킹을 사용하진 않았습니다. 저는 각 물건에서 현재 위치, 나가는 위치, 다른 물건 위치 까지의 거리를 모두 구해준 후 순열로 챙길 물건의 순서를 정해준 뒤 미리 구한 거리 값을 이용하여 최소 거리를 구해줬습니다. 단계 별로 정리하자면 다음과 같습니다. 1. 현재 위치와 챙길 물건들의 위치를 리스트에 저장 2.. 2022. 2. 18.

티스토리툴바