본문 바로가기

dp8

[Java] BOJ 7626 Four Squares 문제 문제 링크 https://www.acmicpc.net/problem/17626라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다.어떤 자연수는 복수의 방법으로 표현된다.예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다.역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다.1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다.좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.자연수 n이 주어질 때, n을 최소 개수의 .. 2024. 7. 31.

[Java] BOJ 11727 2×n 타일링 2 문제 문제 링크 https://www.acmicpc.net/problem/117272×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.아이디어직사각형을 채우는 방법의 수를 저장할 n + 1 크기의 배열을 생성한다.직사각형의 가로가 1일때 방법의 수는 1, 가로가 2일때 방법의 수는 3이기 때문에 배열의 첫번째 값은 1, 두번째 값은 3으로 초기화한다.3부터 n까지 반복을 하는데, 가로가 i인 직사각형을 채울 방법의 수는 가로가 i - 1인 직사각형을 채우는 방법의.. 2024. 7. 30.

[Java] BOJ 11726 2×n 타일링 문제 문제 링크 https://www.acmicpc.net/problem/117262×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.아이디어직사각형을 채우는 방법의 개수를 저장할 n + 1 크기의 배열을 생성한다.가로가 1일때는 방법이 1가지, 가로가 2일때는 방법이 2가지이므로 배열의 첫번째 값은 1, 두번째 값은 2로 초기화함3부터 n까지 반복하는데, 가로 길이가 i인 직사각형을 채우는 방법은 가로가 (i - 1)인 직사각형을 채우는 방법과 가.. 2024. 7. 29.

[Java] BOJ 9461 파도반 수열 문제 문제 링크 https://www.acmicpc.net/problem/9461오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다.첫 삼각형은 정삼각형으로 변의 길이는 1이다.그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다.나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)각 테스트 케이스마다 P(N)을.. 2024. 7. 28.

[Java] BOJ 9095 1, 2, 3 더하기 문제 문제 링크 https://www.acmicpc.net/problem/9095정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 아이디어연산의 개수를 저장하는 배열을 n + 1 크기로 만들고 1은 1, 2는 2, 3은 4로 초기값을 저장해준다.연산의 개수.. 2024. 7. 28.

[Java] BOJ 2579 계단 오르기 문제 문제 링크 \https://www.acmicpc.net/problem/2579계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는.. 2024. 7. 27.

이전 1 2 다음

최근글

인기글

공지사항

최근댓글

티스토리툴바