본문 바로가기

Algorithm123

[Swift][DP] 백준 11052번 (카드 구매하기) 요구능력 : DP의 개념을 아느냐 코드설명 : dp라는것은 만들어진 최대값이 중복하여 쓰인다는것을 보고 알았다. 1. dp에 P1, P2, ... 이 있을 때 P1+P1이 아닌 P2 자신이 최대값이 될 수 있으므로 편하게 비교하기위해 카드의 가격을 넣어준다. 2. dp 1은 비교할게 없으니 2부터 시작해서 최대값이 될 수 있는 숫자를 다 비교해준다. ex) 6개산다고 가정하면 f(6) = f(5) + f(1) f(6) = f(4) + (2) f(6) = f(3) + (3) 과 f(6) 자신이 위의 더한값들보다 클 수 있다. 그래서 아래코드는 하나하나 비교해준 코드이다. 후기 : DP개념을 알고, 최대값이 나오는 경우의수를 알고있으면 풀만한문제 let n = Int(readLine()!)! //구매하려고 .. 2021. 8. 30.
Swift) 백준 9095번 (1, 2, 3 더하기) 요구능력 : DP의 개념을 아느냐 코드설명 : dp[1] = 1 dp[2] = 1 + 1, 2 dp[3] = 1 + 1 + 1, 2 + 1, 1 + 2, 3 위를 보면 1, 2, 3이 dp 3까지 들어가므로 예외(?)로 치고 먼저 선언해줫다. 그리고 for문을 4부터 시작해줫는데 dp[4] 일 때 dp[1] + dp[2] + dp[3] = dp[4]가 되는것을 보고 아래 점화식을 도출했다. dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 후기 : DP개념을 알고, 숫자를 끄적여보면 풀수있는문제.. let T = Int(readLine()!)! var dp = Array(repeating: 0, count: 11) dp[1] = 1 dp[2] = 2 dp[3] = 4 for _ .. 2021. 8. 29.
Swift) 백준 11727 (2 x n타일링2) 요구능력 : 규칙을 통해 DP를 사용해야할지를 아느냐 코드설명 : n이 1 ~ 3일때를 그림으로 보자 문제를 보면 1x2, 2x1, 2x2짜리 타일들을 쓴단다. 그 타일들을 기준잡아서 규칙을 세워봤다. n = 1일 때와 n = 2일 때는 완벽한상태(?)가 아니기 때문에 저걸가지고 규칙을 이야기할수는 없다. 그래서 n = 4까지 손으로 그려봤고 그 결과 위와 같은 규칙이 나왔다. n = 4 이니까 n -1 한 값인 n = 3일 때의 도형들이 2x1도형옆에 붙어서나온거고 n - 2 두개도 같은원리다. 후기 : 나도 이 문제이해를 참 어렵게했다. 설명이 죄다 대충이고 제대로 이해도안하고 글쓰신분들도 많은거 같아서.. 길이가 n인데 1빼서 n -1 인거 가지고 DP문제인걸 어떻게 알겠나 싶었다 ㅋㅋ 왜 DP를 .. 2021. 8. 29.
Swift) 백준 11726번 (2 x n타일링) 요구능력 : 규칙을 통해 DP를 사용해야할지를 아느냐 코드설명 : 2 x 2 ~ 2 x 4까지 그림을 그려보자. 규칙을 찾아보면 아래와 같다. 보다시피 위의 세로막대기가 왼쪽에 1개 있는건 n-1개가 나온다. 아래의 가로막대기가 왼쪽에 2개 있는건 n-2개가 나온다. 여기서 DP를 해야겠다는 생각이 어떻게 나오냐? 1. 문제가 연속적이다. 2. 중복되는 부분문제가 있다. ( f(5)를 구하려면 f(4)와 f(3)을 구해야하는데 f(4)를 구하려면 f(3)을 또 구해야하는 것을 말한다.) 후기 : 규칙을 찾고 DP개념만 알고있으면 풀 수 있는 문제 let n = Int(readLine()!)! var dp = Array(repeating: 0, count: 1001) dp[1] = 1 dp[2] = 2 f.. 2021. 8. 28.

티스토리툴바