본문 바로가기

전체 글

 (31)
[BOJ][DP] 9465. 스티커 문제 -> https://www.acmicpc.net/problem/9465 하나를 선택하면 상하좌우를 선택할 수가 없다. 그러면, 대각선으로만 추가적으로 계속 선택해나갈 수 있다는 말. 근데, 무조건 제일 근접한 대각선에 위치한 값만 가져와서는 안된다. 그 옆에있는 것도 고려를 해서 둘 중 큰 값을 골라야 한다.이런식으로 구상을 할 수가 있다. 점화식은 위 그림을 토대로 dp[0][i] = Max(dp[1][j-1], dp[1][j-2]) + dp[0][i];dp[1][i] = Max(dp[0][j-1], dp[0][j-2]) + dp[1][i];가 되겠다. 배열을 왜 한개만 썼냐면,굳이 두개를 쓸 필요없이 dp배열에 초기값을 넣고서이후 각각의 최댓값만 넣주면 더 이상 쓸 필요가 없기 때문이다. 소스(..
[BOJ][DP] 1010. 다리 놓기 문제 -> https://www.acmicpc.net/problem/1010 이 문제는 DP를 활용한 풀이와 확통의 조합을 사용하여 해결할 수가 있다. 하지만 나는 그냥 DP로 풀어버렸다. 이왕 DP문제인데 DP로 풀어야 재밌지.. 다른 사람들은 죄다 조합으로만 풀더이라. (물론, 확실히 조합이 더 빨라서 그런거겠지만.) 위 그림의 사이트 상태는 N: 3, M: 4 다. 어라? 가만보면 그 속에 (2,3)과 (2,2)가 들어있다. 옳지. 이를 통해 알 수 있는 사실은전에 계산했던 값들을 이용하여 새 DP값을 얻을 수 있다는 것. 일단 N이 1인 경우의 수들을 구해둔 상태를 전제로 해야한다. 위 그림의 동그라미 친 부분처럼,부분적인 경우의 수가 더 이상 없을때까지 계속 더해야한다. 더하는 식은 dp[i][..
[BOJ][DP] 1463. 1로 만들기 문제 -> https://www.acmicpc.net/problem/1463 재귀로 간단히 풀 수 있는 문제이다. 매 재귀마다 연산을 하는 횟수를 증가하며 넘겨준다. 1이 되었을 때 연산 횟수는 점점 줄어들며가지치기가 될 것이다. 고로 바로 해결이 된다. 소스(GitHub)
[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,..

티스토리툴바