https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 난이도 : 실버 3 태그 : 그리디, 정렬 설명 1, 2, 3, 4 위치에서 물이 흐르고, 길이가 3인 테이프가 있다고 할 때, 위치 1을 테이프를 막기 위해 0.5 ~ 2.5 까지 덮을 수 있습니다. 하지만 위치가 3인 곳은 고치지 못하기에, 위치 3을 막기 위해 2.5 ~ 4.5 까지 덮을 수 있습니다. 즉, 물이 새는 곳의 위치를 오름차순 정렬한 뒤, 가장 처음 물이 떨어지는..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 난이도 : 골드 5 태그 : 구현, 시뮬레이션 설명 2차원 블록 세계에 비가 왔을 때, 빗물이 고여있는 양을 구하는 문제입니다. 해당 문제의 경우, 각각의 블록을 기준으로 하여 (왼쪽 블럭 중 가장 큰 값, 오른쪽 블록 중 가장 작은 값) 중 가장 작은 값을 구한 뒤, 기준이 되는 블록의 높이만큼 빼주면 해당 블록에 채워지는 물의 양을 구할 수 있습니다. 빨간색 화살표로 가르키고..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 난이도 : 실버 3 태그 : 구현, 브루트포스 설명 어릴때 많이 해봤던 숫자야구 게임입니다. 프로그래밍 언어를 처음 배울 때 구현 능력 향상 예제로도 많이 접하곤 하죠. 이번 문제는 특이하게도, 숫자와 해당 숫자의 strike, ball이 주어졌을 때, 가능한 정답의 개수를 출력하면 됩니다. 그냥 간단하게, 123부터 시작하여 987 까지(중복이 허용되지 않으므로), 숫자, strike, ball..

https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 난이도 : 실버 5 태그 : 그리디, 정렬 설명 3개를 사면 가장 싼 가격의 제품 하나를 무료로 줍니다. 그냥 단순히 내림차순으로 정렬 후, 가장 비싼 물품과 그 다음으로 비싼 물품을 산 뒤, 3번째로 비싼 물품을 공짜로 받고, 4번째로 비싼 물품과, 5번째로 비싼 물품을 산 뒤, 6번째로 비싼 물품을 꽁자로 받는 과정을 반복하여 풀 수 있을 것 같습니다. 소스코드 fun main() ..

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 그리디, 정렬 설명 문제 자체는 간단합니다. n과, n개의 숫자가 주어질 때 해당 숫자를 잘 조합하여 가장 큰 수를 만드는 문제입니다. 소스코드 첫 번째 시도 import java.util.StringTokenizer fun main() { val n = readln().toInt() val st = StringTokenizer(r..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 난이도 : 실버 5 태그 : 문자열, 정렬 설명 같은 문자는 제거하면서, 길이 순으로 정렬하고, 길이가 같을 땐 사전 순으로 정렬하는 문제입니다. 코틀린, 코딩테스트 둘 다 공부를 시작한지 얼마 안됬을 때 풀었던 문제였던 것 같은데, 옛날에 꽤나 치열하게 풀었더군요... 소스코드 1년 전 코드 fun main() { val case = readLine()!!.toInt() var arr..

https://www.acmicpc.net/problem/4993 4993번: Red and Black There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. Wr www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 전형적인 DFS/BFS로..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색 설명 위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다. 선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다. n이 2 !selected[index] }.sum() // 선거구2 인구 수 answer = minOf(ans..

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 난이도 : 골드 4 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 뮤탈리스크가 SCV(1 ~ 3대)를 때리면 첫 타격때는 9, 둘째 타격때는 3, 셋째 타격에는 1을 줍니다. 이때 SCV를 모두 파괴시키는 최소 공격 횟수를 구하는 문제입니다. 음,,, 너비 우선 탐색으로 접근해야 할 것 같다는 느낌은 빠르게 왔는데, 어떻게 풀지 다소 난해했던 문제였습니다. SCV의 초기 ..

https://www.acmicpc.net/problem/10838 10838번: 트리 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 www.acmicpc.net 난이도 : 플래티넘 5 태그 : 트리, 최소 공통 조상 설명 최소 공통 조상(LCA)를 사용하는 문제이지만, 일반적인 LCA와 달리, 새로운 사용법을 알게 된 문제였습니다. 각 노드의 깊이를 찾기 위해 일반적으로 루트 노드에서 DFS 탐색을 진행하여 각 노드의 부모와 깊이를 알아냅니다. LCA에서 depth를 구하는 이유는 최소 공통 조상을 찾기 위한 과정 중, v1, v2 두 노드가 주어졌을 때..