본문 바로가기

백준177

[Swift][DP] 백준 16194번 (카드 구매하기 2) 요구능력 : DP의 개념을 아느냐 코드설명 : 카드구매하기 위에 링크를 클릭하고 가면 자세한 설명이되어있다. 위의 링크의 코드와 다른점은 기존의 dp[i] 와 dp[i -j] + dp[j] 를 비교하여 더작은값을 dp[i]에 넣는다는 것이다. dp[i] = dp[i-j] + dp[j] > dp[i] ? dp[i] : dp[i-j] + dp[j] 후기 : DP개념을 알고, 최소값이 나오는 경우의수를 알고있으면 풀만한문제 let n = Int(readLine()!)! //구매하려고하는 카드의개수 let arr = readLine()!.split(separator: " ").map{Int($0)!} var dp = Array(repeating: 0, count: 10001) for i in 0.. dp[i] .. 2021. 8. 31.
[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.

티스토리툴바