https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 접근 방식 최악의 경우는 62C3 이므로, 충분히 조합으로 문제를 풀 수 있다. 전체 빈 칸들 중에서 3개를 선택한 모든 경우의 수를 계산해도 되는지 먼저 파악했다. 지도의 가로, 세로 크기는 최대 8이므로, 최대 64개의 칸이 존재할 수 있고, 그 중 바이러스가 최소 2칸을 차지하므로 빈 칸의 개수는 최대 62개이다. 62개 중에서 3개를 순서 상관 없이 고르는 것이므로 위 조합이 나왔고, 대략 2^1..
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 ..