SY DevLog

1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 정육면체를 이루는 주사위를 3면이 다 보이는 경우, 2면만 보이는 경우, 1면만 보이는 경우 이렇게 3가지로 나눌 수 있다. 그리고 각각에 해당하는 주사위의 개수를 N에 대한 식으로 나타내면 다음과 같다. 3면만 보이는 주사위의 개수 : 4 2면만 보이는 주사위의 개수 : 8(N-2) + 4 1면만 보이는 주사위의 개수 : 5(N-2)^2 + 4(N-2) 3면이 보이는 주사위 3면이 보이는 주사위에서 최소값은 한 모서리를 공유하는 주사위의..

9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net b를 기준으로 오름차순으로 정렬하고, b가 같을 때는 a를 기준으로 내림차순으로 정렬한다. 나는 우선순위 큐를 사용하여 b가 작을수록 우선순위가 높고, b가 같으면 a가 클수록 우선순위가 높도록 설정한 뒤, 우선순위 큐에서 범위 (a,b)를 하나씩 꺼내었다. PriorityQueue pq = new PriorityQueue(M, (Range r1, Range r2) -> (r1.b == r2.b) ? r2.a - r1.a : r1.b - r2.b); book 일차원..

1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 자체는 쉬워보였는데 생각하지도 못한 반례가 몇 개 있어서 시행착오를 겪었다. 우선, 양수만 놓고 보면 최대값이 나오기 위해서는 내림차순으로 정렬해서 큰수끼리 차례대로 곱해주면 된다고 생각했다. ex) 5 4 3 2 1 일 경우, (5*4) + (3*2) + 1 = 27 만약에 음수가 존재한다면 음수는 절대 양수와 곱해져서는 안된다. 음수 x 양수는 더 작은 음수가 되기 때문이다. 그래서 음수는 같은 음수와 곱해지거나 혹은, 0과 곱해져서 음수를 상쇄시켜야..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 입력받은 수식의 결과가 최소가 되기 위해서는 먼저 모든 더하기 연산을 한 후, 빼기 연산을 해주면 된다. 우선 입력받은 문자열을 '-'을 기준으로 나눠서 문자열 배열에 담는다. 입력받은 문자열이 55-50+40 이면 "55" 와 "50+40" 로 나누어진다. arr[0] = "55", arr[1] = "50+40" 나누어진 문자열에 '+'가 포함되어 있으면 더하기 연산을 진행한 후 결과값으로 대체한다. 먼저 "55"에는 '+' 문자가 없기 때문에 아무런 처..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 각 사람이 돈을 인출하는데 필요한 시간을 최소로 하기 위해서는 돈을 인출하는데 걸리는 시간이 짧은 사람들부터 돈을 인출하면 된다. 각 사람에게 필요한 시간은 앞사람의 시간이 누적되어 더해진다. 그렇기 때문에 앞사람의 필요시간이 짧으면 짧을수록 누적된 시간이 짧기 때문에 총 합은 줄어들게 된다. 따라서 각 사람의 인출하는데 걸리는 시간을 오름차순으로 정렬한 후, 누적된 합을 더한다. 소스코드 :

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이고, 모든 공간마다 벽으로 ..

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 이다. 이 중에서 가장 큰 ..