1. 문제 N x M의 지도가 주어지며, 이 지도의 각 칸에는 자원이 존재한다. 자원의 양은 정수로 나타난다. 다음 그림은 5 x 6 의 지도에 존재하는 자원을 나타낸다. 철수는 자원을 채취하는 로봇을 갖고 있으며, 이 로봇은 (0, 0) 에서 출발하여 (N-1, M-1) 에서 자원 채취를 마친다. 로봇은 한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것이다. 이 로봇을 이용하여 가장 많이 채취할 수 있는 자원의 양을 출력하는 프로그램을 작성하시오. 위의 예제의 경우 다음과 같이 채취하는 것이 최대이며, 그 양은 49이다. 입력 첫 번째 줄에 N, M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 두 번째 줄부터 N x M 의 지도에 존재하는 자원의 양이 주어진다. 출력 로봇을 이용..

1. 문제 숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다. 45 = 3^2 + 6^2 입력 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 출력 필요한 제곱 수의 최소 개수를 출력한다. 예제 입력 case 1) 45 case 2) 38 예제 출력 case 1) 2 case 2) 3 2. 풀이 이 문제는 점화식을 만드는것이 핵심이다. 점화식을 구하는 순서는 다음과 같다. T(n) = T(a^2 + b^2 + c^2) = 3 T(n-a^2) = T(b^2 + c^2) = 2 즉, T(n) = T(n-x^2..

1. 문제 2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다. 입력 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 ) 출력 가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 예제 입력 case 1) 3 case 2) 8 case 3) 37 예제 출력 case 1) 3 case 2) 34 case 3) 87896 2. 풀이 전형적인 피보나치 수열 문제이다. import java.io.*; public cla..

1. 문제 철수에게는 빨간색, 초록색, 파란색 세 개의 버튼이 있다. 버튼 하나를 누를 때 마다 특정 점수를 얻을 수 있으며, 철수는 1초에 한 번씩 버튼을 누를 수 있다. 물론, 특정 시간에는 세 개의 버튼 중에서 한 개의 버튼만을 누를 수 있다. 각 시간마다 특정 버튼을 눌렀을 때 얻는 점수는 모두 다를 수 있다. 예를 들어, 시간 1에 빨간색, 초록색, 파란색 버튼에 대한 점수가 3, 5, 7 로 주어질 수 있다. 이 경우에는 파란색을 누르는 것이 점수를 가장 많이 얻을 수 있다. 물론, 시간 2에 각 버튼에 대한 점수는 또 다를 수 있다. 버튼을 누를 때에는 한 가지 규칙이 있는데, 연속하여 색깔이 같은 버튼을 두 번 누를 수 없다는 것이다. 예를 들어, 시간 1에 초록색 버튼을 눌렀다면, 시간 ..

1. 문제 N개의 카드가 주어지고, 각각은 자연수의 점수를 가진다. 철수는 이제 이 카드를 가져감으로써 카드에 적혀있는 수 만큼의 점수를 얻는다. 단, 카드를 가져갈 때 한가지 규칙이 있는데, 이는 연속하여 3개의 카드는 가져갈 수 없다는 것이다. 예를 들어, 6개의 카드 “1 3 5 2 7 3”가 주어질 경우, 3+5+7+3 = 18 만큼의 점수를 얻는 것이 최대이다. N개의 카드가 주어질 때, 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 숫자가 주어지며, 이는 각 카드의 점수를 나타낸다. 출력 얻을 수 있는 점수의 최댓값을 출력한다. 예제 입력 6 1 3 5 2 7 3 예제 출력 18 2. ..

1. 문제 철수와 영희는 구슬 게임이 구슬 게임을 하려 한다. 이 구슬 게임의 규칙은 다음과 같다. 철수와 영희는 번갈아가며 구슬을 가져간다. 맨 처음에는 철수가 구슬을 가져간다. 구슬을 가져갈 때에는, 최소 1개에서 최대 3개까지 구슬을 가져갈 수 있다. 가져갈 구슬이 없는 사람이 진다. 예를 들어 5개의 구슬이 있다고 하자. 여기서 철수가 1개의 구슬을 가져가고, 영희가 3개의 구슬을 가져간 후, 철수가 마지막으로 1개의 구슬을 가져갔다고 가정하면 이 게임의 승자는 철수가 된다. 물론, 각자가 어떻게 구슬을 가져가느냐에 따라 승패가 달라질 수 있다. 철수와 영희는 이기기 위해서 최선을 다해서 게임을 플레이 한다. n개의 구슬을 시작으로 게임을 진행한다고 할 때, 철수가 이 게임을 이길 수 있다면 YE..