본문 바로가기

Develop/백준 (python)262

[백준] 1699번: 제곱수의 합 (python) 1699번: 제곱수의 합 문제 ) 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3^2+1^2+1^2(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 1^1=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 출력 : 주어.. 2022. 4. 3.
[백준] 15988번: 1, 2, 3 더하기 3 (python) 15988번: 1, 2, 3 더하기 3 문제 ) 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. - 1+1+1+1 - 1+1+2 - 1+2+1 - 2+1+1 - 2+2 - 1+3 - 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다. 출력 : 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 풀이) 일반적인 dp 풀이 => 규칙 .. 2022. 4. 3.
[백준] 9095번: 1, 2, 3 더하기(python) 9095번: 1, 2, 3 더하기 문제 ) 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. - 1+1+1+1 - 1+1+2 - 1+2+1 - 2+1+1 - 2+2 - 1+3 - 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 : 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 : 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이) 재귀를 이용한 완전 탐색 방식으로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 .. 2022. 4. 3.
[백준] 15486번: 퇴사 2 (python) 15486번: 퇴사 2 문제 ) 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며,.. 2022. 4. 3.

티스토리툴바