SY DevLog

13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 그리디 문제이다. N일째부터 1일째까지 거꾸로 돌면서, n일째에 할 수 있는 과제들 중 가장 점수가 큰 과제를 처리한다. 먼저, 6일째 처리할 수 있는 과제는 5점짜리 과제 하나이다. 따라서 5점짜리 과제를 한다. sum = 5 그 다음 5일째 처리할 수 있는 과제는 하나도 없다. 이미 5점짜리 과제를 해결했기 때문이다. 4일째에 처리할 수 있는 과제는 10점짜리, 40점짜리, 60점짜리가 있다. 이 중에서 가장 큰 점수를 가지는 과제는 60점짜리 과제이다. 따라서 4일째에는 60점짜리 과제를 처리한다. s..

2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net R : 홀수 OR C : 홀수 R, C 둘 중에 하나라도 홀수이면 모든 칸에 있는 기쁨을 다 더할 수 있다. 모든 칸을 다 방문할 수 있다. R : 짝수 AND C : 짝수 문제는 R과 C 둘 다 짝수인 경우이다. R과 C 둘 다 짝수인 경우에는 모든 칸을 다 지날 수 없기 때문에 기쁨의 합이 최대가 되는 방법을 생각해야한다. 처음에는 dfs를 이용하여서 모든 가능한 경로를 다 탐색한 후에 기쁨의 합이 최대가 되는 경로를 출력하도록 했었다. 그러나 결과는 '..

1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net A[r][c]에 대하여 A[r][c]!=B[r][c] 이면, (r, c)를 시작으로하는 3*3 행렬만큼 0은 1로, 1은 0으로 뒤집는다. 위 과정을 r = 0, c = 0 부터 마지막까지 반복한다. 이렇게 하는 이유는 만약에 A[0][0]!=B[0][0] 라면 B[0][0]와 같게 하기 위해 A[0][0]를 뒤집어야 한다. 그런데 A[0][0]를 뒤집기 위해서는 결국 (0,0)을 맨 왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다. A[0][1]도 마찬가지이다. A[0][1]..

1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 어려워서 오래 걸렸던 문제.. 다른 풀이를 참고해서 문제를 해결하였다. 해결 방법은 다음과 같다. 1. 1부터 N까지를 오름차순으로 정렬한다. (ex. N = 13, M = 5, K = 4) 2. 수열을 M묶음으로 나눈다. 이때 하나의 묶음에는 숫자가 K개 혹은 그 이하가 들어있어야 한다. 또한, 적어도 하나의 묶음은 K개의 수가 존재해야 한다. 3. M개의 묶음으로 나누었으면 각각의 묶음 내의 수들을 내림차순으로 정렬한다. M묶음으로 나누는 이유는 각각의 묶음에서 숫자 하나씩 선택을 하면 M개의 증가하는 수열을 만들 수 있다. 아래 그림에서 묶음1에서는 4를, 묶음2에서는 7, 묶음3에서는 8, 묶음4에서는 ..

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과 곱해져서 음수를 상쇄시켜야..

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