Swift ) BOJ- 11053 가장 긴 증가하는 부분 수열(Lower Bound)
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 안녕하세요. 후르륵짭짭 입니다. 알고리즘은 참,,,, 쉽지 않습니다. 예전에 푼 문제인데,,,, 오랜만에 풀려고 하니 못 풀었네요 ㅎㅎㅎㅎ. 일단 저는 이 문제를 Lower Bound로 풀었습니다. ** 정답 코드 ** import Foundation let N = Int(readLine()!)! let list = readLine(..
2020. 7. 3.
Swift)BOJ - 1699 제곱수의 합(DP)
안녕하세요. 후르륵짭짭 입니다. www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 이 문제를 풀었는데,,, 시간초과 부분을 어떻게 해결하면 좋을까 많은 고민을 했습니다. DP 문제이기 때문에,, 현재 index에서 절반 까지 확인 하고 가장 작은 것을 찾는 방법으로 짰는데,,, 시간초과,,, 예를들어 ) 12 = list[11] + list[1] = list[10] + list[2] = list[9] + list[3] =..
2020. 7. 3.
