본문 바로가기

23

[Swift][DP] 백준 15988번 (1, 2, 3더하기 3) 요구능력 : DP에 대한 이해 코드설명 : 문제를 설명해주면 1과 2와 3중 한개 이상을 더해서 주어진 수를 만드는 문제이다. 처음 접해보시는 분들은 어렵게 느껴질 수도 있는데, 이 문제만 정확히 이해하면 다른 더하기 DP문제들은 꽤 쉽게 풀릴것이다. 그림을 보면 파란색글씨로 + 1, + 2, +3 을 해놓은것을 볼 수 있다. 1, 2, 3더하기니까 이렇게 1, 2, 3을 기준으로 앞에 들어와야 할 수를 구해준다. 이게 가능한건 DP이기 때문에 가능하다. +1, +2, +3앞에 오는 수가 무엇이든간에 이미 1과 2와 3의 조합으로만 더해놨기 때문이다. 위의 그림에 5를 보면 이전에 4를 1과 2와 3의 조합으로 해놨기 때문에, 4에 조합된 개수를 그대로 가져오는걸 볼 수 있다. 이해가 안간다면 여러번보고.. 2021. 11. 2.
[Swift][DP] 백준 15990번 (1, 2, 3 더하기 5) 요구능력 : DP의 개념을 알고 규칙을 찾을 수 있느냐 코드설명 : 맨 오른쪽 수를 기준으로 규칙이 나온다. 1, 2, 3으로만 더하라고 했고, 중복된 수가 없어야한다고 했다. 수가 n이라고 가정하면, f(n) (n - 1) + 1 (n - 2) + 2 (n - 3) + 3 이 있다. 위 그림과 같이 f(5)까지 있다고 가정하면 아래와 같은 규칙이 나온다. f(5)의 4 + 1에서 4는 f(4)에 있는 2 + 2와 1 + 3으로 대체된다. 배열을 보면 dp[i][1] dp[i][2] dp[i][3] 이 있다. dp[i][1]은 수의 마지막자리가 1인 수의 개수를 저장 dp[i][2]은 수의 마지막자리가 2인 수의 개수를 저장 dp[i][3]은 수의 마지막자리가 3인 수의 개수를 저장 dp[i][1] = .. 2021. 8. 31.
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.

티스토리툴바