문제

숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.

45 = 3^2 + 6^2

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

필요한 제곱 수의 최소 개수를 출력한다.

예제 입력

45

예제 출력

2

예제 입력

38

예제 출력

3

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution07.java

문제

2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )  

출력

가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예제 입력

3

예제 출력

3

예제 입력

8

예제 출력

34

예제 입력

37

예제 출력

87896

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution06.java

문제

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

입력

첫 번째 줄에 철수에게 주어진 시간 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄부터 N개의 시간에 대하여 빨간색, 초록색, 파란색 버튼을 눌렀을 때 얻을 수 있는 점수가 주어진다.

출력

철수가 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력

3
27 8 28
18 36 40
7 20 8

예제 출력

87

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution05.java

문제

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

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution04.java

문제

철수와 영희는 구슬 게임이 구슬 게임을 하려 한다. 이 구슬 게임의 규칙은 다음과 같다.

1. 철수와 영희는 번갈아가며 구슬을 가져간다. 맨 처음에는 철수가 구슬을 가져간다.
2. 구슬을 가져갈 때에는, 최소 1개에서 최대 3개까지 구슬을 가져갈 수 있다.
3. 가져갈 구슬이 없는 사람이 진다.

예를 들어 5개의 구슬이 있다고 하자. 여기서 철수가 1개의 구슬을 가져가고, 영희가 3개의 구슬을 가져간 후, 철수가 마지막으로 1개의 구슬을 가져갔다고 가정하면 이 게임의 승자는 철수가 된다. 물론, 각자가 어떻게 구슬을 가져가느냐에 따라 승패가 달라질 수 있다. 철수와 영희는 이기기 위해서 <b>최선을 다해서 게임을 플레이 한다.</b> n개의 구슬을 시작으로 게임을 진행한다고 할 때, 철수가 이 게임을 이길 수 있다면 YES, 그렇지 않다면 NO를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 전체 구슬의 개수n 이 주어진다. (0 ≤ n ≤ 1,000,000)  

출력

첫째 줄에 철수가 이길 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

예제 입력

3

예제 출력

YES

예제 입력

5

예제 출력

YES

예제 입력

191124

예제 출력

NO

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution03.java

문제

N x M 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.

입력

첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형이 주어진다. 직사각형 안의 숫자 S는 -100이상 100이하이다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다. (1 ≤ a,c ≤ N, 1 ≤ b,d ≤ M)
 

출력

각 질문에 대한 답을 출력한다.

예제 입력

5 5 3
 1 -2 3 2 8
-8 -9 3 4 5
 2 4 7 8 2
 1 4 3 1 4
-1 2 5 -6 3
1 2 3 4
0 0 1 1
2 0 2 1

예제 출력

37
-18
6

문제풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution02.java

문제

숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.  

예제 입력

4

예제 출력

7

예제 입력

200

예제 출력

290816

출처

Taejon 2001 PC번  

문제 풀이

https://github.com/JK921/icandoit/blob/develop/multicampus/src/Solution01.java

회고

풀이

3 3 5
1 3 10
1 2 5
2 3 3
1 3 4
3 1 100

10

소스