https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 접근 방식 치킨 집과 가정 집의 좌표를 원소로 갖는 리스트를 각각 생성하자 치킨 거리를 구하는 방법이 치킨 집과 가정 집의 좌표로 구해지므로, 이 문제에서 필요한 것은 오직 치킨 집과 가정 집의 위치 정보다. 그리고 여러 개의 치킨 집 중에서 m개만 뽑는 조합(nCm)을 구해야 하는데, 치킨 집의 인덱스를 가지고 각 조합을 표현할 예정이므로 리스트를 생성해야 한다. 2차..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 1. 접근 방식 작은 문제들을 모아 큰 문제를 해결하는 다이나믹 프로그래밍 기법이다 k원을 구성하는 최소 동전들의 개수는 (k - coin)원을 구성하는 최소 동전 + 1이다. 따라서 1원부터 k원까지 점진적으로 각 금액을 구성하는 최소 동전 개수를 구하면 문제를 해결할 수 있다. 인덱스 i원을 만드는 최소 동전 개수를 담은 1차원 dp 배열을 선언하자 최소 동전 ..
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 접근 방식 dfs로 접근하면 안 된다 시작점과 끝점이 명확한 그래프 문제처럼 보이지만, DFS로 풀면 시간 초과가 발생한다. bfs로도 접근하면 안 된다 (a - 1, b)에서 (a, b)를 방문하게 되는 경우와 (a, b - 4)에서 (a, b)를 방문하게 되는 경우는 서로 다르게 취급되어야 한다. 그러나 bfs에서 각 노드의 방문 여부를 나타내는 visited라는 배열은 (a ..
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. 접근 방식 구현 방식의 문제임을 파악하자 문제가 주절주절 길다. 지문이 이렇게 긴 이유는, 문제를 해결하기 위한 여러 조건들을 제시하기 때문이다. 그럼 문제를 꼼꼼히 읽으면서 주어진 조건대로 구현하기만 하면 된다. 미세먼지 확산을 구현할 때, 확산된 양 ⌊Ar,c/5⌋을 담은 배열 amount와 변경된 결과를 담을 배열 updated를 추가로 생성하자 한 번 확산이 완료되면 기존 (r, c..