문제 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 풀이 입력받은 좌표에 음식물을 표시하고, BFS 탐색을 통해 음식물의 크기를 계산하여 풀이하면 된다. BFS 함수에서는 Queue에서 좌표를 추가할 때마다 갯수를 세어준다. 그리고 BFS 함수에서 음식물의 크기를 반환하도록 하여 최대값을 찾아 출력해주면 된다. 코드 import java.util.* data class Point(val x: Int, val y: Int) fun main() { val br = Sys..

문제 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 수열(LIS, Longest Increasing Subsequence)을 구하는 문제로, 동적 프로그래밍(DP)을 활용하여 해결할 수 있다. 입력받은 배열에서 반복문을 통해 현재 위치에서 앞의 원소들의 값과 비교하며 값을 갱신하면 된다. 만약 앞의 원소가 현재 원소보다 작다면 상자에 넣을 수 있으므로 해당 위치의 값 + 1을 현재 위치의 DP값과 비교하여 갱신해주면 된다. [1, 6, 1, 7, 5, 8]에 대해 LIS을 구하는 알고리즘을..

문제 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 DFS를 활용해 순열 사이클을 구할 수 있다. 입력받은 배열에는 다음으로 이동할 위치를 가르키고 있기 때문에 현재 위치는 방문 표시를 해주고 가르키는 위치로 DFS 탐색을 해주면 된다. 만약 현재 위치에서 가르키는 위치가 이미 방문했던 위치인 경우, 순열 사이클이 만들어진 것이다. 반복문을 통해 각 위치에서 시작하는 사이클을 구하면 되는데, 이미 방문했던 위치는 사이클에 포함되어 ..

문제 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 풀이 이분 탐색을 이용해 필요한 경기 수를 구할 수 있다. 이분 탐색은 주어진 범위에서 중간 값을 선택하고, 그 값이 원하는 조건을 만족하는지에 따라 탐색 범위를 좁혀가는 방식이다. 이 문제에서는 승률을 계산하여 승률이 언제 변하는지 확인하고, 그에 따라 탐색 범위를 조절하면 된다. 승률 계산에서 소수점은 버려야하기때문에 승률은 floor(100*win/match) 으로 계산한다. 이분 탐색은 입력받은 경기 수까지의 범위에서 실행하면 된다. 코드 i..

문제