개발하는 고라니

17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net [DFS + 동적 프로그래밍] 동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고... 이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net [비트마스킹 + DP] 처음에 문제를 보고 최소 스패닝 트리 문제인 줄 알았다. 그래서 크루스칼 알고리즘을 사용해서 풀 수 있겠다 싶었지만, 최소 스패닝 트리와 완전히 달랐다. 최소 스패닝 트리는 한 정점이 2개 이상의 간선을 가질 수 있지만, 외판원 순회의 경우 한 정점은 2개만 갖을 수 있다. 그리고 반드시 출발점 -> ... -> 출발점이 되어야한다. 이때의 최소값을 구하는 문제였던 것이다. DP와 DFS에 취약한 내 ..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [DFS + 동적 프로그래밍] 가로 세로 대각선 그림처럼 다음 파이프를 놓는 것은 현재 파이프가 어떻게 놓여져 있는지에 의존한다. 그래서 dp[n][n][3]이라는 배열을 사용했고, dp[n][n][0]은 가로로 놓여져 있을 때, dp[n][n][1]은 대각선, dp[n][n][2]는 세로로 놓여져 있을 때의 경우의 수를 나타낸다. 그리고 대각선의 경우 대각선을 나타내는 좌표 뿐 아니라, 좌측, 상측 모두 빈공간이어야 함을 명심해야한다. ..

1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [동적 프로그래밍 (메모제이션)] 특별한 방법이 사용되지는 않는 문제이다. 왼쪽의 사이트가 n개이고, 오른쪽의 사이트가 m개일 때 다리를 놓을 수 있는 경우의 수가 dp[n][m]이라면, dp[1][1] = 1 dp[2][1] = 0 dp[3][1] = 0 dp[4][1] = 0 dp[1][2] = 2 dp[2][2] = 1 dp[3][2] = 0 dp[4][2] = 0 dp[1][3] = 3 dp[2][3] = 3 dp[3][3] = 1 dp[4][3] = 0..

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net # 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. # 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 10..

11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net # 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. # 입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. # 출력 첫째 줄에 길이..

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net # 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다...