https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net DFS + 다이나믹 프로그래밍 어떤 한 좌표 (i, j)에 도달할 수 있는 경우의 수는, 주변 4방향 중 (i, j)보다 높은 곳에 도달할 수 있는 경우의 수의 합과 같다. 문제에서는 내리막길을 사용해서 (N, M)에 도달해야 한다고 적혀 있는데, 이는 반대로 말한다면 (N, M)부터 (1, 1)까지는 오르막길이라는 뜻이다. 이에 따라 다음과 같은 DFS 함수를 선언했다. private stat..
DP
https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 다이나믹 프로그래밍 DP 모든 경우의 수를 찾는 것이므로 DP를 사용하여 풀었다. 파이프가 두 칸을 차지할 수 있기 때문에, 파이프의 r 값이 가장 작은 칸, 만일 r이 같다면 c값이 가장 작은 칸을 기준으로 파이프의 개수를 세도록 했다. 어떤 칸 (i, j)에 파이프가 존재할 수 있는 경우는 세 가지이다. 1. (i, j + 1)도 빈 칸이어서 파이프를 가로로 둔다. 2..
https://www.acmicpc.net/problem/10942 [10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net](https://www.acmicpc.net/problem/10942) DP i부터 j까지의 숫자가 팰린드롬이라는 것을 확인하는 방법은 무엇일까? 만일 i번째 숫자와 j번째 숫자가 같은 경우, i + 1부터 j - 1까지가 팰린드롬이면, i부터 j까지도 팰린드롬이다. 이를 바탕으로 이차원 배열을 사용한 dp로 구현했다. 가장 먼저 팰린드롬인지 여부를 나타내는 2차월 배열 p를 init해준다. N의 최댓값이 2,000인데 비해 질문의 ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 다이나믹 프로그래밍 포도주를 마시는 효주에게는 세 가지 상태가 있고, 각 상태에서 효주가 고를 수 있는 선택지도 정해져 있다. 0. 이전 잔을 안 마신 상태 : 현재 잔을 마시면 1번 상태로 가고, 마시지 않으면 0번 상태에 머무른다. 1. 직전에 한 잔 마신 상태 : 현재 잔을 마시면 2번 상태로 가고, 마시지 않으면 0번 상태로 간다. 2. 직전에 두 잔 마신 상태 : 현재 잔을 마실 수 없으므..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 골드 5 접근 방법 1 : 처음 생각 난 dfs로 풀어보았다. 파이프가 놓인 방향이 가로면 0, 대각선이면 1, 세로면 2로 방향을 정한 후, 각 방향마다 조건을 따져서 위치를 일일이 옮겨주었다. 파이프의 끝부분이 (N-1, N-1)이 될 때까지 계속 진행하도록 하였다. N의 범위가 작아서 시간 초과가 나오지는 않았지만, 21일 java 기준 1724/1801등으로 다른 ..
