SY DevLog

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 한 개의 강의실에 최대한 많은 회의를 넣기 위해서는 각 회의마다 끝나는 시간을 기준으로 오름차순 정렬을 해줘야 한다. 왜냐하면 앞에 회의가 일찍 끝날수록 뒤에 더 많은 회의가 회의실을 사용할 수 있기 때문이다. 먼저, 회의의 시작 정보와 끝나는 정보를 담은 Class 클래스를 생성하였다. 그리고 끝나는 시간이 짧은 순서대로 우선순위를 두어서 모든 Class를 우선순위 큐에 넣는다. 가장 먼저 큐에서 빠져나오는 회의는 모든 회의들 중 가장 일찍 끝나는 회의가 될 것이다. 예를 들어 문제 예제에서 (1, 4), (3, 5), (0..

11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 통나무를 선형으로 배열하는 것이 아니라 원형으로 배열하기 때문에 처음과 끝이 만난다. 그러므로 통나무를 단순히 오름차순, 혹은 내림차순으로 정렬하면 최소 난이도를 구할 수 없다. 예를 들어 오름차순으로 정렬하면 가장 왼쪽에는 최소값, 가장 오른쪽에는 최대값이 배치되는데, 원형이기 때문에 둘 사이의 차이도 난이도에 포함된다. 최대값에서 최소값을 뺀 값은 가장 큰 차가 되므로 최소 난이도를 구할 수 없다. 그래서 최소 난이도를 구하기 위해서는 중간에 위치한 통나무의..

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net room 이차원 배열을 만들어서 방번호를 넣어준다. room 이차원 배열이 여기서 방문처리 역할을 한다. room[m][n] != 0 이미 방번호가 배정된 것이므로(방번호는 1번부터 시작하는 걸로 설정) 방문한 것이나 마찬가지가 된다. area 일차원 배열에는 해당 방들의 넓이를 넣어준다. ex) area[1] : 1번 방의 넓이, area[2] : 2번 방의 넓이 문제에서 성곽의 최대 넓이는 n=50, m=50 일 때 2500이고, 모든 공간마다 벽으로 ..

9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 해시맵을 사용하여서 key값으로는 옷의 종류(headgear, eyewear, face)가 들어가고, value로는 종류별로 옷의 개수를 넣는다. 첫번째 예제의 경우 headgear가 2개, eyewear가 1개이므로 (key = headgear, value = 2), (key = eyewear, value = 1) 이 해시맵에 들어간다. 옷을 입는 조합은 알몸인 경우만..

2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이분탐색으로 풀었다. 위의 예제에서 -99 -2 -1 4 98 이 주어질 때, -99와 더해서 0이 되려면 99라는 수가 필요하다. 그러면 -99 보다 오른쪽에 있는 -2 1 4 98 중에서 이분탐색을 이용하여 99와 가장 가까운 수를 찾아서 -99와 더한다. -> -99 + 98 = -1 그 다음, -2와 더해서 0이 되려면 2라는 수가 필요하다. -2보다 오른쪽에 있는 1 4 98 중에서 이분탐색을 통해 2와 가장 가까운 수를 찾아서 -2와 더한다. -..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제를 보자마자 플로이드 워셜 알고리즘이 떠올랐다. 어느 회원과 다른 회원과의 점수는 노드 사이의 거리라고 생각할 수 있다. 어느 회원 노드에 대해서 다른 모든 회원 노드와의 거리를 구하고, 그 중에서 가장 큰 거리가 그 회원의 점수가 된다. 모든 회원에 대하여 다른 회원과의 거리를 알아야 하므로 플로이드 워셜 알고리즘을 사용하면 된다. 예를 들어, 문제의 예제에서 1번 회원은 2,3,4,5번 회원과의 거리가 각각 1, 2, 2, 3 이다. 이 중에서 가장 큰 ..

www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net HashMap을 사용하여서 쉽게 풀었다. 맵의 Key에는 종 이름을, Value에는 종의 개수를 새어서 증가시켜준다. 소스코드 :

2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색으로 문제를 해결할 수 있다. 이분탐색을 진행하면서 중간값(mid)이 블루레이 최소 크기의 후보가 된다. 각 레슨의 길이가 저장된 배열을 차례대로 탐색하여 한 블루레이당 레슨 길이의 합이 mid보다 작도록 레슨을 그룹으로 분리한다. 예를 들어, mid = 15 이고, 레슨의 길이가 차례대로 1 2 3 4 5 6 7 8 9 이면, 한 블루레이당 레슨 길이의 합이 mid보다 작도록 나누면 (1,2,3,4), (5,6), (7), (8), (9) 로 나눌 수 있다. ..

6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이분탐색으로 문제를 풀었다. 이분탐색의 먼저 범위(left ~ right)를 정해야 한다. left : 현우가 N번 동안 필요한 금액 중 최대값이 이분탐색 범위의 시작값이 되어야 한다. 예를 들어 현우가 n번째에 500원이 필요한데, 한 번에 인출할 수 있는 금액이 500원보다 작은 400원 이라면 현우는 n번째에 돈을 쓸 수가 없다. right : 현우가 N번 동안 필요한 금액의 총 합이 이분탐색 범위의 끝값이 된다. 이분탐색을 진행하면서 현우가 통장에서 인출해야할..

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(Trie)를 이용하여 문제를 해결하였다. 트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다. 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 전화번호에 일관성이 없는 경우는 트라이에..