dp9 [JAVA67] 1699. 제곱수의 합 1699. 제곱수의 합 (S2)시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB652752675319511 40.058 %문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.입력.. 2024. 10. 31. [JAVA64] 2294. 동전2 2294. 동전2 (G5)시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초128 MB802552501717756 30.095 % 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. summary합 K 만들 때 사용되는 동전 최소.. 2024. 10. 27. [JAVA62] 1904. 01타일 1904. 01타일 (S3)시간 제한메모리 제한제출정답맞힌 사람정답 비율0.75 초256 MB1102473616028677 31.770 % 문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있.. 2024. 10. 25. [JAVA56] 1065. 한수 1065. 한수 (S4)시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초128 MB1528568436569895 54.822 %문제어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. summary한수의 개수 출력 각 자리수가 등차수열을 이루는 수 (1, 12, 123)strategyDP 활용1부터 99 는 등차수열임 (99보다 작으면 N 이 정답)100자리 이상은 맨 .. 2024. 10. 18. [JAVA43] 9251. LCS 9251. LCS (G5)시간 제한메모리 제한제출정답맞힌 사람정답 비율0.1 초256 MB942343928028794 41.036 % 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. summary 두 문자열의 LCS의 길이를 출력 ( Longest Common Subsequence, 최장 공통 부분 수열) strateg.. 2024. 10. 1. [JAVA 37] 10844. 쉬운 계단 수 10844. 쉬운 계단 수 (S1)시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB 154771 50291 36781 30.884 % 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다summary길이가 N인 계단 수가 총 몇 개 있는지 구하기 계단수란 인접한 모든 자리 차이가 1인 계단 strategyDP 활용 (N 이 최대 100 이라서 완전 탐색 X) 계단 길이.. 2024. 9. 25. 이전 1 2 다음