💻 Problem문제 보러 가기 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자. 💡 Approach임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.문제에서 이런 조건이 주어진다.어떤 한 회의는 이전 회의와 다음 회의와 겹친다.따라서..

💻 Problem문제 보러 가기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다.벌레는 기준연도 1년 2월에 1마리가 탄생한다.벌레는 매년 1월이 되면 분열한다. 분열 시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.홀수 연도에 탄생한 개체는 3번 분열 시, 짝수 연도에 탄생한 개체는 4번 분열 시 사망한다.예를 들어, 기준년도 1년 2월에 존재하던 벌레는, 2년 1월, 3년 1월, 4년 1월에 분열하고 사망하여 4년 말에는 존재하지 않게 된다. 이때, N 년 말에 존재하는 벌레의 수를 구하여라. 💡 Approach먼가.. 문제를 읽어 보니 DP겠다 싶어서..

💻 Problem문제 보러 가기 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. ✏️ Solution 1import sysinput = sys.stdin.readlinen = int(input(..

💻 Problem문제 보러 가기 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. n은 양수이며 11보다 작다. 💡 Approach dp[1] = 1dp[2] = 2dp[3] = 4dp[4] = 7dp[5] = 13...직접 세보면서 점화식을 구한다.dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 예를 들어, dp[5]의 경우, 5를 1, 2, 3 조합으로 더해야 한다.1로 시작하는 조합, 2로 시작하는 조합, 3으로 시작하는 조합을 구해보면 아래..

💻 Problem문제 보러 가기 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 💡 Approachdp 배열에서 index는 현재 금액이고 value는 N가지 동전으로 현재 금액을 만들 수 있는 방법의 수이다. 예를 들어, 2원과 4원으로 8원을 만든다고 하겠다.N=2, coins=[2, 4], M=8우리가 간단히 생각해 본다면 2+2+2+2, 2+2+4, 4+4 세 가지 ..

💻 Problem문제 보러 가기 45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 💡 Approach이게 실버 문제라니! DP 너무 어려웡ㅠ처음 접근할 때는 수의 첫 번째 자리를 기준으로 생각했다.맨 처음에는 9개의 숫자가 올 수 있고.. 그다음 자리는 2개의 숫자가 올 수 있고..0이나 9일 때를 고려해야 하고.. 너무....복잡햇......... 이 글을 보고 이해할 수 있었다.음음.. 가장 끝 자리에 오는 숫자를 기준으로 했어야 하는 거구나 i는 자릿수이고 j는 끝자리 숫자이다.예를 들어, i=2, j=4, dp[2][4]=2이면 두 자릿수..

💻 Problem문제 보러 가기 효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야 한다.길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라. 💡 Approach문제에서 a[i] = a[1] + (i - 1)를 만족해야 한다고 나와있다.이 식은 등차가 1인 등차수열이다.즉, a[i] = a[i - 1] + 1을 만족하면 된다. 해당 문제의 시..

💻 Problem문제 보러 가기 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1 ^ 2의 합이다; 또한 4 ^ 2 + 3 ^ 2 + 1 ^ 2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125 ^ 2 + 6 ^ 2 + 1 ^ 2 + 1 ^ 2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105 ^ 2 + 15 ^ 2 + 8 ^ 2 + 5 ^ 2.자연수 n이 주어..