문제 1059번: 좋은 구간1 이상 N 이하의 정수들이 있을 때, 주어진 수 x를 포함하면서 x보다 크지 않은 수만을 사용하는 연속 구간들을 ‘좋은 구간’이라 한다. x가 주어질 때 좋은 구간의 개수를 구하는 문제.www.acmicpc.net 풀이 집합에 포함된 구간 내에서는 조건을 만족할 수 없기 때문에, 먼저 해당 수(num)가 집합에 포함되어 있는지 여부를 확인해 따로 처리한다. 그 후, 조건을 만족하는 시작점(start)과 끝점(end)을 찾기 위해 입력받은 배열의 각 원소를 num과 비교하면서 num보다 작은 수 중 가장 큰 값, 그리고 num보다 큰 수 중 가장 작은 값을 각각 갱신한다. 이렇게 구한 두 경계값 사이에서 가능한 구간의 개수를 계산해 최종적으로 조건을 만족하는 구간의 수를 ..

문제 1236번: 성 지키기성의 세로 길이 N과 가로 길이 M이 주어진다. 각 칸은 ‘X’ 또는 ‘.’로 표시되며, ‘X’는 이미 경비가 있는 방, ‘.’은 없는 방이다. 각 행과 열마다 최소 하나의 경비가 있어야 할 때, 추가로 설치해야 할 최소 경비의 수를 구하는 문제.www.acmicpc.net 풀이 이 문제는 모든 행과 열에 최소 한 명의 경비원을 배치해야 하는 문제다. 각 행과 열을 각각 확인하면서, 아무도 배치되어 있지 않은 행과 아무도 배치되어 있지 않은 열의 개수를 구한다. 모든 행과 열에 한 명 이상 배치해야 하므로, 그 중 더 많이 필요한 쪽의 수가 필요한 최소 경비원 수가 된다. 코드 fun main() { val (n, m) = readln().split(' ').map {..

문제 5568번: 카드 놓기고유한 카드 N장을 이용해서 서로 다른 수를 만들려고 한다. 카드를 순서대로 나열했을 때 만들 수 있는 서로 다른 수의 개수를 구하는 문제.www.acmicpc.net 풀이 백트래킹과 HashSet을 이용해 해결할 수 있다. 입력받은 숫자들을 이용해 만들 수 있는 모든 조합을 백트래킹으로 탐색하며, 각 조합을 문자열 형태로 HashSet에 저장한다.HashSet은 중복을 허용하지 않기 때문에 모든 탐색이 끝난 뒤 집합의 크기(hashSet.size)가 곧 만들 수 있는 서로 다른 정수의 개수가 된다. 코드 fun main() { val n = readln().toInt() val k = readln().toInt() val arr = Array(n){ re..

문제 1388번: 바닥 장식첫 줄에는 세로 길이 N과 가로 길이 M이 주어진다. 다음 N개의 줄에는 바닥 타일의 상태가 '-' 또는 '|'로 주어진다. 같은 종류의 타일이 연속으로 이어져 있을 때, 하나의 장식으로 계산한다. 바닥 장식의 최소 개수를 구하는 문제.www.acmicpc.net 풀이 이 문제는 바닥 장식을 이루는 나무 판자(-, |)의 개수를 세는 문제다. 서로 연결된 같은 모양(- 또는 |)은 하나의 판자로 취급해야 한다. 이를 위해 가로 방향 탐색과 세로 방향 탐색을 각각 한 번씩 수행하여 판자의 개수를 계산한다. - 가로 방향 탐색 각 행(i)을 왼쪽에서 오른쪽으로 확인하며, 이전 문자와 다를 경우 새로운 판자가 시작된 것으로 판단해 cnt++을 수행한다. 단, 세로 판자(|)가 등..

문제 9237번: 이장님 초대농부 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.www.acmicpc.net 풀이 그리디 유형의 문제다. 자라는데 가장 오래 걸리는 나무부터 먼저 심는 것이 최적의 선택이다. 따라서 입력받은 나무의 성장 시간을 내림차순(역순) 으로 정렬한 뒤, 각 나무를 심는 순서에 따라 필요한 날짜를 계산해준다. 모든 나무 중에서 가장 늦게 자라는 나무의 날짜를 계산하여 값을 출력한다. 코드 fun main() { val num = readln().toInt() val arr = readln().split(' ').map { it.t..