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/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/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 ..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들자. C 중에서 B보다 작으면서 가장 큰 수 구하기 0으로 시작하면 안 됨 이 문제가 까다로웠던 것은 문자열과 숫자와의 변환이 헷갈려서! 0으로 시작하면 안 되니까 그것도 체크해줘야 한다! 우선 모든 순열을 구해봤다. 아슬아슬하게 통과.. [모든 순열을 구한 경우] -> 676ms 🚨 import F..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 연속 3잔 모두 마실 수 없음 최대한 많은 양의 포도주 마시기. 최대양 출력! 주의할 것은 연속 3잔은 마실 수 없다는 것! i번째까지 마셨을 때, 최대양을 구하면서 진행하기 4번째까지 왔다고 해보자. 4번 잔을 마시는 경우 - dp[1] + 3번 잔 + 4번 잔 (3 연속피하기) - dp[2] + 4번 잔 (3 연속피하기) 4번 잔을 마시지 않는 경우 -> dp[3] import Foundatio..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net N일동 안 최대한 많은 상담 상담에 걸리는 시간 Ti, 상담 시 금액 Pi 백준이가 얻을 수 있는 최대 수익은? i일에 얻을 수 있는 최대 이익(dp[i]) 중 최대 이익 구하기 2중 for문 - i일에 상담해도 되는지 체크 (상담 기간 n일 넘으면 안 됨) - i일에 상담한다고 했을 때, 얻는 금액 - 0~i-1일을 순회하면서 - j일에 상담하면 i일에 상담할 수 있는지 체크 - 상담할 수 있다면, 금액 합치기 -> 여기서 그동안 dp[i]에 저장된 금액과 비교해서 최대 금액으로 갱신 [DP] import Foundation //i..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net X에서 사용하는 연산 3으로 나누어 떨어지면, 3으로 나누기 2로 나누어떨어지면 2로 나누기 1 빼기 연산을 사용하는 횟수의 최솟값 1~N을 쭉 보면서 저 연산들을 사용해서 1을 만들 수 있는 방법의 횟수 최솟값 구하기 2의 배수 min(2로 나눈 값, 이전 dp + 1) 3의 배수 min(3로 나눈 값, 이전 dp + 1) 나머지 이전 dp + 1회 3의 배수 먼저! 큰 애를 먼저 나눠야 횟수가 적음 import Foundation //input let n = Int(readLine()!)! var dp = ..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 이 문제는 DP 또는 Greedy로 풀 수 있는데, DP 연습을 하고 있기 때문에 DP로 풀어봤다! 우선, 차분히 예제를 두고 쭉 적어봤다. 규칙을 찾아야 하기 때문! - 3의 배수 - 5의 배수 - 3와 5의 합으로 나올 수 있는 수 그런데 쭉 숫자들을 적어 내리다 보니, 8(3+5) 이후로는 3과 5로 모두 나타낼 수 있었다! 그래서, 초기값을 3, 5, 6으로만 주고 8 이후로 작은 문제의 답으로 큰 ..