본문 바로가기

BOJ

 (22)
[BOJ][DP] 2167. 2차원 배열의 합 문제 -> https://www.acmicpc.net/problem/2167 그림을 그려서 생각을하면 간단히 풀리는 문제. (애초에 문제는 거의 다 그림으로 풀지만..) 이 문제의 설명이 오해의 소지가 있다..[i][j] 부터 [x][y]까지의 합이라는 의미는 아래의 의미다.처음에 잘 못 이해하는바람에 왜 틀리는지 이해가 안갔었다. 그냥 무작정 (i, j) ~ (x, y)의 합을 구해도 정답이 뜬다고는 하는데, 시간복잡도가 점점 커질 수 밖에 없다. 그래서 효율적으로 각 dp배열에 (1,1)부터 자신까지의 합을 구해놓는다. 그러믄, 합을 구하는 점화식을 생각해보자. 빨간색 체크표시가 된 위치를 dp[x][y]라 치자. 각각 다른색으로 칠해진 사각형은 이미 구해진 dp 값이다.일단 더하자.dp[x][y] ..
[BOJ][DP] 11052. 붕어빵 문제 -> https://www.acmicpc.net/problem/11052 한 참 생각한 후에야 풀었다. 간단히 생각한다면, 한 쪽은 세트 순서값이 내려가고, 한 쪽은 세트 순서값이 올라가며 제일 큰 값을 얻어내는 방법이다. 세트를 저장하는 배열과 dp값을 저장하는 배열을 나눠야 한다.그렇지 않으면, 원하지 않는 결과가 등장하게 된다. 소스(GitHub)
[BOJ][DP] 11048. 이동하기 문제 링크 -> https://www.acmicpc.net/problem/11048 꽤 간단한 DP 문제라고 생각한다. 현 위치를 (x , y)라 할 때, 가능한 이동 방법은(x+1, y), (x, y+1), (x+1, y+1) 이렇게 세가지이다. 그런데, 가만 생각해보면 굳이 대각선으로 갈 필요가 없지 않나?대각선으로 바로 통과하는 것 보다 한 곳을 더 거쳐서 가는게 더 사탕을 많이 먹을 수 있을텐데? 위 사진에서 볼 수 있듯이 바로 대각선 이동 보다는 우->하 or 하->우 로 가는것이 더 최대의 이익을 누릴 수 있다. 따라서 나는 대각선으로 가는 경우는 그냥 배제해버렸다. 고로 점화식은 아래와 같이 나온다. dp[i][j] = Max(dp[i-1][j], dp[i][j-1]) + maze[i][j]..
[BOJ][DP] 2156 포도주 시식 https://www.acmicpc.net/problem/2156 개인적으로 생각하는데 꽤 시간이 든 문제.. 지금 돌아보니 그렇게 오래 걸릴 문제는 아닌 것 같은데.. 뭐, 다 그런게지. 이 문제에서의 포인트. 연속으로 놓여있는 3개 이상의 포도주를 마실 수 없다. DP는 항상 어려운게, 점화식 하나 세우는게 힘들다. 작은 경우에서 큰 경우로 확장을 시키면서 점화식을 만들어야 하는게 DP의 포인트. ~식으로 ~처리가 되어서 결국 마지막에 x 값이 제일 큰 값이 된다. 라는 전개를 해야한다. 포도주의 용량을 담는 배열을 wine. 각각의 dp값을 담는 dp배열이 있을 때, N개의 와인이 있으면, 시식하는 3가지의 경우가 발생한다. 1. N번째 와인을 마시고 N-1, N-3 와인을 ..
[BOJ][DP]9005 1,2,3 더하기 https://www.acmicpc.net/problem/9095 이 문제는 규칙을 파악하는 문제다. 필자도 아무리 생각해도 갈피를 못 잡아 인터넷 참고를 조금 했다. - 풀이 - n = 1 일때, ( 1 )로, 경우의 수는 1개.n = 2일때, (1 + 1), ( 2 )로, 경우의 수는 2개.n = 3일때, (1 + 1 + 1), (1 + 2), (2 + 1), ( 3 )으로 경우의 수는 4개. n = 4는 문제 예시에 나와있으므로 7개. 어라? n = 1~3 까지의 경우를 더한게 n = 4의 경우의 수랑 같네? 위의 사실로는 n[i] = n[i-3] + n[i-2] + n[i-1] 과 같다. 우연일지도 모른다. 그래서 일단 위의 가설을 전제로 n = 7까지 계산해보자. n = 5, 13개 n = 6,..
[BOJ][DP] 1932. 숫자삼각형 https://www.acmicpc.net/problem/1932 DP 문제다. 문제에서 우리가 잡아내야 할 포인트는 1. 이제까지 선택된 수의 합이 최대가 되는 경로.2. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼/오 중 하나를 선택. 점화식을 세우기 위해서 일단 이해를 해보자. 문제에서는 수들을 삼각형의 형태로 나타내었지만, 어렵게 생각할 필요가 없다.위에서부터 차례대로 배열에 넣어주면 아래와 같다. 그럼 여기서 어떻게 어떠한 값에 대한 왼/오 대각선 값을 가리킬 수 있을까? 보다시피 한 값의 인덱스 +2 = L, +3 = R 이 되는것을 알 수있다. 얼추 이해가 오기 시작하는가?그렇다면 이제 여태까지 이해한 것을 바탕으로 점화식을 세워보자.(arr은 입력받았던 값을 저장해둔 배열이다.)..

티스토리툴바