문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 방법 이전 위치 + 현재 위치의 정보를 바탕으로 다음 줄로 계속해서 내려갔을 때 최소 점수와 최대 점수를 구하는 문제다. DP를 이용해서 풀어야한다는 것을 알 수 있지만, 모든 줄의 정보를 저장하면 메모리 초과가 발생한다. 처음엔 int dp[2][100001][3]으로 했었는데 메모리 초과가 발생했다. 단순히 계산해보면 2 * 3 * 100,001 + 3 * 100,001 = 대략 900,000개의..
DP
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 방법 1005번 ACM Craft와 비슷한 문제다. 위상 정렬과 DP를 활용하는 문제이므로 잘 모르겠다면 위 링크를 통해 설명을 보는 것을 추천한다. 위 문제와 차이점은 입력 형식이 다르다는 점, 모든 건물의 건설 완성 시간을 출력해야 하는 점이다. 코드 #include #include #include #include using namespace std; int main() ..
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 방법 항상 낮은 칸으로 이동하며 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 갈 수 있는 경로의 개수를 구하는 문제다. 처음엔 단순한 탐색문제인 줄 알고 모든 케이스를 다 탐색해서 개수를 구하려고 했다. 하지만 최악의 경우를 생각해본다면 한 정점에서 4방향으로 모든 정점을 계속해서 탐색할 수도 있기 때문에 다른 방법이 필요하다. 좀 더 생각해보면, 어떤 점(y, x)에서 제일 오른쪽..
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 방법 위상 정렬과 DP에 대해 알고 있어야 하는 문제다. 잘 모르겠다면 바킹독님 블로그나 라이님 블로그를 봐보자. (실제로 내가 알고리즘 공부를 하며 계속 방문중인 블로그들이다.) 건설 순서에 따라 위상 정렬을 진행해주면서 각 건물의 최소 건설 시작 시간을 갱신해주면 된다. 다시 말해, dp[i] = i번 건물을 짓기 시작하는 데 걸리는 최소 시간(최소 건설 시작 시간), buil..
