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 # 처음에 그냥 숫자 3개씩 N줄을 m에 다 입력받고 풀었는데 메모리 초과가 났다. # 메모리제한이 4MB로 매우 작다. 따라서 dp배열도 N줄으로 만들면 안되고 3칸씩 2줄을 선언해서 계속 반복해주어야 한다. 입력되는 숫자들 역시 한번에 입력받으면 안되고 dp테이블을 갱신해줄때마다 한줄씩 입력받아 그때그때 처리를 해줘야 한다. # 최대점수, 최소점수를 구해야 하므로 min_dp, max_dp 배열 두개를 사용..
https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net # 각 좌표마다 경우의 수가 3가지이므로(가로, 세로, 대각선) 3차원 배열을 사용하였다. # 처음 파이프는 (0, 0), (0, 1)에 가로로 놓여있으므로 dp[0][1][0]에 1을 넣어준다. -> (0, 1)에 파이프 끝이 있고, 가로로 놓여있다는 뜻이다. (dp[x][y][0] = (x, y)에 파이프 끝이 있고, 가로로 놓여있다는 뜻 dp[x][y][1] = (x..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 일단.. 노트나 종이에 손으로 하나하나 경우의 수를 세면서 따져본다. (그러면서 규칙이 발견되길 기도한다.) 보통 DP문제는 앞에서부터 하나하나 세거나, 뒤에서부터 하나하나 세다보면 규칙이 보이는 경우가 많다. # dp[N][K]를 K개의 수로 N을 만드는 방법이라고 하자. dp[0][1] = 1, dp[1][1] = 1... dp[N][1]은 1개의 수로 N을 만드는 방법이므로 무조건 1이다. 또한, dp[0][K] 역시 K개의 수로 0을 만들어야 하므로 0만 더해야한다. -> dp[0][K]도 무조건 1이다. # 이..
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net # DP문제이다. 1. 우선 게임판 m을 입력받고 dp테이블도 m과 같은 크기로 선언해준다. 2. (0,0)부터 한 칸씩 이동하며 m[i][j]가 0이면 continue하고, 아니면 점프를 뛸 수 있는지 판단한다. (11, 13줄) 3. 점프를 뛸 수 있으면, 점프를 뛴 곳의 dp값의 현재 좌표의 dp값을 더해준다. 4. 맨 오른쪽 아래인 dp[-1][-1]을 출력한다. import s..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 간단한 DP문제이다. 1. 우선 dp배열을 N만큼 선언해주고, 포도주의 양을 입력받아 grape배열에 넣는다. 2. N==1일 때는 포도주가 1개이므로 grape[0]을 출력하고, N==2일 때는 두 잔 다 마시면 되니 grape[0] + grape[1]을 출력한다. 3. N이 3개이상일 때부터 Bottom-Up방식으로 dp테이블을 갱신해주면 된다. # i번째 잔을 고를 때 최댓값은 다음 3가지 케..
https://leetcode.com/problems/decode-ways Decode Ways - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com * 문제해석: 1 -> 'A', 2 -> 'B', 3 -> 'C' ... 26 -> 'Z' 이런식으로 디코딩을 할 수 있다. Incoding된 문자열을 Decoding하려면 모든 숫자를 '그룹화'한 다음 다시 문자로 mapping 해야한다. ex) "11106"을 mapping하는 경우 "AAJF" with the g..
https://leetcode.com/problems/coin-change/ Coin Change - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com * 문제해석: 주어진 coins배열의 동전들을 가지고 amount에 해당하는 값을 만들 때, 필요한 동전의 최소 갯수를 return, 만들 수 없으면 -1 return # DP문제이다. Greedy문제인 '거스름돈 문제'와 비슷해 보이지만, 이 문제는 coins의 동전들이 다른 동전의 배수가 아닐 수 있으므로(배수인..
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net # N의 개수에 따라 일단 노가다로 직접 세보았다. N = 1 -> 1 N = 2 -> 00, 11 N = 3 -> 001, 100, 111 N = 4 -> 0011, 0000, 1001, 1111, 1100 N = 5 -> 00001, 00100, 10000, 11001, 10011, 00111, 11100, 11111 # 1개, 2개, 3개, 5개, 8개, 13개... 그냥 피보나치수열처럼 이전 두..
모르는 사이에 조금씩 조금씩..
