다이나믹프로그래밍6 [Swift][DP] 백준 11058번 (크리보드) 요구능력 : DP 코드설명 : 의식의 흐름대로 문제를 풀게됬다. 일단 2번부터 4번조건은 처음에는 세개가 다같이 발동해야한다. 1번부터 6번까지는 그냥 A를 찍는게 수가 훨씬 많다고 생각해서 dp[i]에 i를 넣어주었다. 그리고 i가 7일때 부터는 전체선택, 복사, 붙여넣기 등의 과정이 들어가는게 A를 더 많이 찍게된다. n이 7일 때를 가정해서, 점화식을 구해보면 버튼을 총 7번 누를 수 있는데 이 중에서 전체선택, 복사, 붙여넣기를 하려면 버튼 누르는 수가 3번이 있어야한다. 그럼 우리는 A를 최대한 찍고 저 3번을 눌러야한다. 그렇기 때문에 바로 dp[i - 3]인 곳에서 전체선택,복사,붙여넣기를 하면 버튼은 총 7번 누르게된다. 그리고 붙여넣기를 했기 때문에 dp[i - 3]의 A의 개수에서 2배.. 2022. 3. 2. [Swift][DP] 백준 2294 (동전 2) 요구능력 : DP 코드설명 : dp의 초기값을 10001로 설정해준 이유는 이 문제가 최솟값을 찾는 문제이기 때문에 최대값으로 설정해준것이다. 10001이 최댓값인 이유는 k의 범위가 10000까지 이기때문에 여기서 나올 수 있는 가장 큰 수는 1로 10000까지 만들어서 1이 10000개인 경우이다. 위의 사진은 직접 행과 열로 나열해서 사용해야하는 동전의 개수를 적은것이다. 1원으로 1~15까지 만들 수 있는 경우의 수는 1개 ~ 15개이다. 하지만, 5원으로 1 ~ 15까지 만드려면? 뭔가 복잡해지는것 같을 수 있다. 우선, 1원으로 1 ~ 15까지 만들어보자. 행과 열을 만들어야겠다. for i in 0.. 2022. 2. 21. [Swift][DP] 백준 10422번 (괄호) 요구능력 : 다이나믹프로그래밍 코드설명 : 후기 : 상당히 어려운문제 이런생각을 대체 어떻게해서 풀어야하지.. 하지만 뭔가 얻어가는듯한 문제이다. let t = Int(String(readLine()!))! var dp = Array(repeating: 0, count: 5001) dp[0] = 1 dp[2] = 1 for n in stride(from: 4, through: 5000, by: 2) { for i in stride(from: 2, through: n, by: 2){ dp[n] += dp[i - 2] * dp[n - i] dp[n] %= 1000000007 } } for _ in 0.. 2022. 2. 7. [Swift][DP] 백준 1495번 (기타리스트) 요구능력 : DP활용 코드설명 : 문제에서의 핵심 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다. 점화식 dp[i][j] = i는 몇번째 곡 인지, j는 볼륨이다. dp[3][4] = true 이면 3번째곡에서 4의 볼륨을 공연할수 있다는 의미이다. 후기 : dp에 true/false를 넣는것부터 참신한 문제..?인것같다. 진짜 점화식만 잘세우면 푸는문제.. let nsm = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nsm[0] //연주할 곡의 개수 let s = nsm[1] //.. 2022. 1. 11. 이전 1 2 다음
