https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net dp [1][i] = i자리가 1인 경우 dp[0][i] = i자리가 0인 경우 1 2 3 4 5 6 ----------------- 0 | 0 1 1 2 3 5 1 | 1 0 1 1 2 3 개수를 세보면서 진행하면 규칙이 보인다! dp[1][i]는 dp[0][i-1]의 값과 동일하고 dp[0][i]는 dp[0][i-1] + dp[1][i-1] 값이다! //input let n = In..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net i번째 열에서 1행 스티커를 선택한 경우, 2행 스티커를 선택한 경우를 나눠서 진행하면 된다. 상하좌우가 붙으면 안 되니까 한 열에 하나의 행만 선택하고, 이전 열 혹은 전전 열의 다른 행을 선택한 경우를 봐야 한다. 전전 열을 봐야 해서 맨 앞에 0을 추가하고 진행해 줬다. 아니면 1열의 전전 행은 -1 이니까... 맨 앞에 원소를 넣어서 1 열부터 스티커가 있다고 가정하고 시작하기...

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net //(1)1 -> 1^2 //(2)2 -> 1^2 + 1^2 //(3)3 -> 1^2 + 1^2 + 1^2 //(1)4 -> 2^2 //(2)5 -> 1^2 + 2^2 //(3)6 -> 1^2 + 1^2 + 2^2 //(4)7 -> 1^2 + 1^2 + 1^2 + 2^2 //(2)8 -> 2^2 + 2^2 //(1)9 -> 3^2 //(2)10 -> 1^2 ..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수가 뭔지만 안다면 쉽게 풀 수 있는 문제였다.피라미드 형태로 되어있지만 한쪽으로 쭉 밀면 2차원 배열로 나타나는데 좌측 상단쪽의 대각선의 원소와 행 기준 윗 원소를 더하면 현재 원소 값을 구할 수 있다. dp 배열을 사용해서 앞서 저장된 값을 사용해서 빠르게 진행~ import Foundation //input let nk = readLine()!.split(separator: " ").map{ Int(String($0))! } let (n, k) = (nk[..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 감소하는 수 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 예를 들어, 321, 950. 322, 958 안됨. N번째 감소하는 수를 출력하라. 아랫 자릿수로 갈수록 숫자가 작아지면 되는데, 이때 숫자가 같으면 안 된다. 백트래킹으로 앞 원소의 값보다 크거나 같은 수는 잘라냈다. 1자리부터 10자리까지 BT를 진행했다. 감소하는 수를 구했을 경우, 몇번째 감소하는..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통부분 수열은 연속적으로 공통부분 수열을 찾는 게 아니라, 중간중간 다른 값이 있어도 된다..! ACAYKP, CAPCAK 를 보면 ACAK 가능한 모든 경우를 구하려면 시간초과가 발생하므로 이럴 땐, dp! 이런 유형은 어떻게 해야 할지 모르겠어서 찾아봤더니, | A C A Y K P -------------- C | A | P | C | A ..