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/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 cost 배열에는 한 칸에 3개의 값을 저장하도록 했다. 오른쪽에서 왔을 때, 왼쪽에서 왔을 때, 그리고 직진했을 때의 연료 양의 합이다. 1. right : (i - 1, j + 1)에서 대각선으로 올 때 2. left : (i - 1, j - 1)에서 대각선으로 올 때 3. straight : (i - 1, j)에서 직진해서 올 때 연속으로 ..
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등으로 다른 ..
