1.
직각삼각형의 둘레가 120일 때, 세 변의 길이가 모두 양의 정수인 직각삼각형은 다음과 같이 3가지입니다.
(20, 48, 52), (24, 45, 51), (30, 40, 50)
1 이상 N 이하의 둘레 중에서, 세 변의 길이가 모두 양의 정수인 직각삼각형을 가장 많이 만들 수 있는 둘레와 그때 만들어지는 직각삼각형의 개수를 구하는 프로그램을 작성하세요.
입력 #1
120
입력값 설명
첫째 줄에 양의 정수 N이 주어집니다. (12 ≤ N ≤ 2,400)
단, 세 변의 길이가 모두 양의 정수인 직각삼각형을 최소 1개 이상 만들 수 있는 입력만 주어집니다.
첫째 줄에 정답을 출력합니다. 단, 조건을 만족하는 둘레가 여러 개인 경우 그 중에서 가장 작은 둘레를 출력합니다.
출력 #1
120 3
2.
배열 a에 1부터 N까지의 양의 정수가 각각 2개씩 포함되어 있습니다. 즉, 배열 a의 길이는 2N입니다.
a의 i번째 원소를 a_i라고 할 때, 다음 조건을 만족하는 a를 “좋은 배열”이라고 정의합니다.
•
모든 정수 i, j, p, q (1 ≤ i < j < p < q ≤ 2N)에 대해 a_i = a_p이면 a_j ≠ a_q이다.
배열 a가 주어질 때, 배열 a가 좋은 배열인지 아닌지 판단하는 프로그램을 작성해주세요.
입력 #1
3
2 1 1 2 3 3
첫째 줄에 양의 정수 N이 주어집니다. (2 ≤ N ≤ 1,000)
둘째 줄에 2N개의 양의 정수 a_1, a_2, …, a_2N이 공백으로 구분되어 주어집니다. (1 ≤ a_i ≤ N)
출력 #1
YES
좋은 배열이면 “YES”, 좋은 배열이 아니면 “NO”를 출력합니다. (큰 따옴표 제외)
3.
철수가 사는 동네는 N개의 구역과 M개의 단방향 도로로 구성되어 있습니다. 각 구역에는 1번부터 N번까지 번호가 붙어있고, 철수는 1번 구역에 있습니다.
철수는 소화도 시킬 겸 동네를 산책하려고 합니다. 그런데 도로들이 모두 단방향이므로, 처음에 출발했던 구역으로 다시 돌아오지 못할 수도 있습니다.
구역과 도로들의 정보가 주어졌을 때, 철수가 처음 출발했던 1번 구역으로 돌아올 수 있는지 판단하는 프로그램을 작성해주세요. 단, 1번 구역 외 다른 구역을 적어도 한번은 거쳐야 산책으로 인정됩니다.
첫째 줄에 구역의 개수와 단방향 도로의 개수를 의미하는 양의 정수 N과 M이 공백으로 구분되어 주어집니다. (2 ≤ N ≤ 100, 1 ≤ M ≤ 500)
이어서 M개의 줄에 걸쳐 단방향 도로의 시작 구역의 번호 s와 도착 구역의 번호 e가 주어집니다. 이는 해당 도로를 통해 s번 구역에서 e번 구역으로 이동할 수 있음을 의미합니다. 단, s ≠ e이며 s번 구역에서 e번 구역으로 향하는 간선은 단 하나만 존재합니다.
입력 #1
3 3
1 2
2 3
3 1
출력 #1
YES
다른 구역을 거쳐 1번 구역으로 돌아올 수 있으면 “YES”, 돌아올 수 없으면 “NO”를 출력합니다.
4.
N개의 정점과 M개의 양방향 간선으로 이루어진 그래프가 주어집니다. 정점에는 1번부터 N번까지 번호가 붙어있습니다. 또한, 정점마다 가중치가 부여되어 있습니다. 어떤 정점 하나를 선택하고 해당 정점의 가중치를 1 높일 때마다 비용이 1만큼 발생합니다.
그래프의 모든 이웃한 정점 간 가중치 차이를 K 이하가 되도록 만들기 위해 필요한 최소 비용을 구하는 프로그램을 작성해주세요.
입력 #1
3 3 5
1
10
20
1 2
2 3
1 3
첫째 줄에 정점의 개수 N, 간선의 개수 M, 가중치 차이 K가 공백으로 구분되어 주어집니다. (2 ≤ N ≤ 50, 1 ≤ M ≤ 200, 1 ≤ K ≤ 100)
이어서 N개의 줄에 걸쳐 i번 정점의 가중치를 의미하는 양의 정수 s가 주어집니다. (1 ≤ s ≤ 1,000)
이어서 M개의 줄에 걸쳐 간선의 정보를 의미하는 양의 정수 u, v가 주어집니다. 이는 u번 정점과 v번 정점을 연결하는 간선이 존재함을 의미합니다. 즉, u번 정점과 v번 정점이 이웃합니다.
출력 #1
19
그래프의 모든 이웃한 정점 간 가중치 차이를 K 이하가 되도록 만들기 위해 필요한 최소 비용을 출력합니다.
5.
일차원 세계의 지형은 땅과 바다 둘뿐입니다. 이 세계의 지도는 알파벳 소문자 'g'와 'o'로 이루어진 문자열입니다. 'g'는 땅을, 'o'는 바다를 의미합니다.
그런데 아뿔싸, 재승이가 지도에 잉크를 쏟아 일부 문자를 알아볼 수 없게 되었습니다. 지도에서 땅인지 바다인지 알 수 없게 된 부분은 'x'로 표시됩니다.
일차원 세계의 지도가 주어지면 가능한 섬의 개수의 최솟값과 최댓값을 알려주세요. 섬이란 양옆이 바다인 연속한 땅입니다.
입력 #1
oxxxo
한 개의 줄에 일차원 세계의 지도가 주어집니다. (3 ≤ 지도의 길이 ≤ 100)
지도의 첫 문자와 마지막 문자는 'o'(바다)임을 보장합니다.
출력 #1
0
2
첫번째 줄에 섬의 개수의 최솟값을 출력합니다.
두번째 줄에 섬의 개수의 최댓값을 출력합니다.
6.
3x3 체스판에 흰색 나이트 2개와 검정 나이트 2개가 주어집니다.
모든 흰색과 검정색 나이트의 위치를 서로 바꿀 수 있는지 판단해주는 프로그램을 작성하세요.
나이트의 이동 규칙은 다음과 같습니다.
편의상 체스판을 직교 좌표계로 나타내어 어떤 나이트가 (x, y)에 위치한다고 가정합시다.
그러면 그 나이트는 다음 8개의 좌표들 중 다른 기물이 없는 체스판 위로 이동할 수 있습니다.
(x-1, y+2), (x+1, y+2), (x-2, y+1), (x-2, y-1), (x+2, y-1), (x+2, y+1), (x-1, y-2), (x+1, y-2)
입력 #1
010
001
220
입력 #2
010
020
120
첫째줄 부터 3줄에 걸쳐 현재 체스판의 상태가 주어집니다
0은 빈칸, 1은 흰색 나이트, 2는 검정 나이트를 의미합니다.
출력 #1
possible
출력 #2
impossible
흰색과 검정색 나이트의 자리를 바꿀 수 있으면 “possible”, 바꿀 수 없으면 “impossible”을 출력하세요.
7.
철수와 영희는 카드 게임을 즐겨합니다. 철수와 영희가 플레이하는 카드 게임에서는 N개의 카드가 포함된 덱을 사용하고, 각 카드에는 양의 정수가 적혀있습니다. 카드 게임의 규칙은 다음과 같습니다.
1.
플레이어는 번갈아가면서 게임을 진행합니다.
2.
플레이어는 자신의 차례가 되면 덱의 가장 위에서부터 1개 이상 3개 이하의 카드를 가져갑니다. 카드를 가져간 플레이어는 가져간 카드에 적힌 수들의 합만큼 점수를 획득합니다.
3.
모든 카드를 가져갔을 때 점수가 높은 플레이어가 게임에서 승리합니다.
철수와 영희는 카드 게임을 여러번 플레이하다보니 승패에 관심이 사라졌습니다. 대신 게임이 끝났을 때 (철수의 점수 - 영희의 점수)를 최대로 만들면 얼마가 될 지 궁금해졌습니다. 철수와 영희를 위해 (철수의 점수 - 영희의 점수)의 최댓값을 구하는 프로그램을 작성해주세요.
첫째 줄에 카드의 개수를 의미하는 양의 정수 N이 주어집니다. (1 ≤ N ≤ 1,000)
둘째 줄에는 덱의 위에 있는 카드부터 순서대로 각 카드에 적힌 양의 정수 N개가 공백으로 구분되어 주어집니다. 카드에 적힌 양의 정수는 100 이하입니다.
입력 #1
3
5 1 6
입력 #2
6
5 5 1 5 5 5
출력 #1
12
출력 #2
24
첫째 줄에 (철수의 점수 - 영희의 점수)의 최댓값을 출력합니다.
8.
끝없이 넓은 평면의 땅이 있습니다. 직선 울타리 만을 이용해서 N 명에게 나눠줄 땅을 구획하려면 최소 몇 개의 직선이 필요한가요?
이때 나뉜 땅을 모두 나눠 줄 필요는 없지만, 한 명에게 최소 한 구역의 땅을 나눠주어야 합니다.
첫째줄에 정수 N(1 ≤ N ≤ 1000) 이 주어집니다. N 명에게 나눠주기 위한 땅을 구획하기 위한 직선 울타리의 최소 개수를 출력하세요.
입력 #1
2
출력 #1
1
9.
부분 행렬이란 주어진 행렬의 일부 열과 일부 행을 지워서 만들어 낸 더 작은 행렬을 말합니다.
정수로만 이루어진 행렬과 정수 X가 주어졌을 때, 성분의 합이 X와 같은 부분행렬이 존재하는지 알아내는 프로그램을 작성해봅시다.
첫째 줄에 행렬의 크기 행과 열의 개수를 나타내는 N, M과 X가 공백으로 구분되어 주어집니다. (1 ≤ N, M ≤ 4, -1000 ≤ X ≤ 1000)
둘째 줄부터 N줄에 걸쳐, 행렬이 주어집니다. 행렬의 각 원소는 절대값이 1000이하인 정수입니다.
성분의 합이 X와 같은 부분행렬이 존재하면 YES, 그렇지 않으면 NO를 출력합니다.
입력 #1
2 2 5
7 -2
1 0
입력 #2
3 3 2
-5 4 1
3 4 -3
5 -1 6
출력 #1
YES
출력 #2
NO
10.
치훈이는 생일 선물로 배열 A를 받았습니다.
A의 서로 다른 네 인덱스 i, j, k, l에 대하여,
A_i * A_j = A_k * A_l를 만족하는 i, j, k, l가 존재하는지 출력하세요.
A_i는 배열 A의 i번째 원소를 뜻합니다.
첫 줄에 N이 주어집니다. (4 ≤ N ≤ 50)
두번째 줄에 길이 N의 배열 A가 공백으로 구분되어 주어집니다. (1 ≤ A_i ≤ 1000)
존재하면 YES, 아니면 NO를 출력합니다.
입력 #1
4
1 2 3 6
입력 #2
6
56 23 79 81 27 29
출력 #1
YES
출력 #2
NO
11.
현민이는 재수 끝에 우주경찰대학교에 입학하였고, 마침내 졸업하게 되었습니다. 결과적으로 발령을 받게 되어 첫 번째 임무를 맡게 되었습니다. 그 임무란 바로 세기의 도둑 재우를 포획하는 임무입니다.
재우는 일직선 상의 우주 공간에 숨어 있습니다. 일직선 상의 우주 공간은 위치 N으로 표시할 수 있으며 현민이는 현재 K 위치에 있습니다. 현민이는 워프 기술을 이용해 재우를 가장 빠르게 포획하고자 합니다.
현민이의 위치를 X라고 했을 때, 현민이는 워프 기술을 이용해서 (X + 3), (X - 1), (X * 2)의 위치 중 한 곳으로 이동할 수 있습니다. 이 때 재우를 잡기 위한 최소 워프 횟수를 구하는 프로그램을 작성하세요.
예를 들어 현민이의 위치가 20이고, 재우의 위치가 89라고 했을 때 최소 워프 횟수는 (20, 40, 43, 86, 89)로 4번이 될 것입니다.
첫 번째 줄에 현민이가 있는 위치 K와 재우가 있는 위치 N이 주어집니다. (0 <= K, N <= 100,000)
현민이가 재우를 포획하기 위한 최소 워프 횟수를 구합니다.
입력 #1
20 89
입력 #2
47898 5783
출력 #1
4
출력 #2
42115
12.
치훈이는 팔찌를 여러 개 가지고 있습니다. 팔찌는 1개 이상의 보석들이 원형으로 배열되어 있는 형태입니다. 팔찌 2개의 보석 배열 상태가 주어졌을 때, 두 팔찌가 같은 팔찌인지 판별하세요.
두 팔찌가 같다는 것은, 팔찌를 회전하여 같은 형태로 만들 수 있다는 것을 말합니다. 단, 팔찌를 뒤집을 수는 없습니다.
팔찌 2개가 두 줄에 걸쳐 주어집니다.
각 팔찌는 알파벳 대문자로 이루어진 문자열의 형태로 주어집니다.
같은 문자는 같은 보석을 뜻합니다.
문자열의 길이는 1000 이하입니다.
두 팔찌가 같으면 YES, 다르면 NO를 출력합니다.
입력 #1
ABCDE
CDEAB
입력 #2
AAAAA
AAAAB
출력 #1
YES
출력 #2
NO
13.
준하는 산책하는 것을 좋아합니다.
준하가 사는 동네는 무한한 크기의 격자입니다. 준하는 매일 이 격자의 변을 따라 산책을 합니다. 어느 날, 매일 똑같은 산책길에 질린 준하는 특별한 방식으로 산책을 하기로 했습니다.
집에서 출발해 격자의 변을 따라 한 칸 전진한 다음, 무조건 좌회전이나 우회전을 합니다. 그 후에 또 한 칸 전진하고, 또 좌회전 또는 우회전 합니다. 이를 총 N번 반복합니다.
하지만 같은 길을 또 걷는 건 지루하기 때문에, 이전에 걸었던 격자의 변이나 꼭지점은 다시 걷지 않으려고 합니다.
준하가 이런 식으로 산책을 할 때, 서로 다른 산책길의 수를 출력하는 프로그램을 작성해 주세요.
산책길의 궤적이 동일하더라도 이동 방향이 다르면 다른 경로로 간주합니다. 하지만 회전했을 때 완전히 같은 산책길은 같은 산책길로 간주합니다.
첫째 줄에 N이 주어집니다. (1 ≤ N ≤ 20)
서로 다른 산책길의 수를 출력합니다.
입력 #1
4
입력 #2
8
출력 #1
6
출력 #2
42
14.
님비 현상은 Not In My BackYard의 약자로, 공공의 이익에는 부합하지만, 자신이 속한 지역에는 이롭지 아니한 일을 반대하는 행동을 뜻합니다.
수직선 위에 N개의 집이 있습니다. 그 중 한곳을 골라 쓰레기 소각장을 지으려고 합니다. 공공의 이익이 되는 시설이므로 가까울수록 주민의 만족도가 늘어나지만, 너무 가까우면 오히려 만족도가 줄어듭니다.
이를 명확하게 정의하면 다음과 같습니다. 쓰레기 소각장과 집까지의 거리를 d라고 할 때, 쓰레기 소각장과 거리가 K이하인 집은 d만큼의 만족도를, K초과인 집은 -d만큼의 만족도를 갖게 됩니다.
모든 집의 만족도의 합을 최대화 하기 위한 쓰레기장의 위치를 출력하는 프로그램을 작성해 주세요.
첫째 줄에 N과 K가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 100,000)
이어서 다음 줄에, 수직선 위의 집의 좌표 A_i, N개가 공백으로 구분되어 주어집니다. (1 ≤ A_i ≤ 100,000)
모든 집의 만족도의 합을 최대화 하기 위한 쓰레기장의 위치를 출력합니다.
만약 그런 위치가 여러개라면, 가장 좌표가 작은 곳을 출력합니다.
입력 #1
5 2
1 3 5 7 8
입력 #2
5 5
1 3 5 7 8
출력 #1
5
출력 #2
3
15.
길에 N개의 싱크홀이 생겼습니다. 이 싱크홀을 그대로 놔두면 위험하기 때문에, 준하는 가지고 있는 길이가 K인 널빤지를 이용해 임시로 보수하려고 합니다. 싱크홀의 위치와 널빤지의 길이가 주어질 때, 싱크홀을 모두 덮기 위한 널빤지의 최소 개수를 출력하는 프로그램을 작성해 주세요.
첫째 줄에 N과 K가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 100,000)
둘째 줄에 싱크홀의 위치 A_i가 공백으로 구분되어 주어집니다. (1 ≤ A_i ≤ 100,000)
싱크홀을 모두 덮기 위한 널빤지의 최소 개수를 출력합니다.
입력 #1
5 3
5 3 8 10 1
입력 #2
2 1
4 5
출력 #1
3
출력 #2
2
16.
준하는 블로그를 운영하고 있습니다. 용돈을 벌고 싶었던 준하는 블로그에 광고를 달려고 합니다.
광고를 달기 위해서는 블로그의 방문자 수가 많을 수록 유리합니다. 블로그의 관리자 메뉴에는 N일간의 방문자의 수가 기록되어 있는데, 준하는 이 기록중 연속된 K일만 빼고 모두 삭제해서 평균 방문자가 더 많은 것처럼 만드려고 합니다. 가장 많은 평균 방문자가 표시되도록 하기 위해서는 몇 번째 날 부터 K일만 남겨야 하는지 계산하는 프로그램을 작성해 주세요.
첫째 줄에 N과 K가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 5,000, 1 ≤ K ≤ N)
둘째 줄에 i일째의 방문자 수를 나타내는 A_i가 공백으로 구분되어 주어집니다. (1 ≤ A_i ≤ 1,000)
가장 많은 평균 방문자가 표시되도록 하기 위해서는 몇 번째 날 부터 K일만 남겨야 하는지 출력합니다. 그런 날이 여러 개라면, 가장 빠른 날을 출력합니다.
입력 #1
5 2
7 4 2 1 8
입력 #2
6 3
1 2 3 4 5 6
출력 #1
1
출력 #2
4
17.
준하는 아침에 일어나기가 힘듭니다. 그래서 알람을 맞춰 놓아도 바로 일어나지 못해서 알람이 여러번 울리도록 설정해 놓았습니다. 처음 알람이 울린 다음, 두 번째 알람은 1분 후, 세 번째 알람은 두 번째 알람이 울린 다음 2분후, ..., K번째 알람은 K-1번째 알람이 울린 다음 K-1분 후에 울립니다.
준하가 알람을 맞춘 시각이 주어질 때, N번째 알람이 울리는 시각을 출력하는 프로그램을 작성해 주세요.
첫째 줄에 알람을 맞춘 시각이 HH:MM형태로 주어집니다.
둘째 줄에 N이 주어집니다. (1 ≤ N ≤ 1,000,000,000)
N번째 알람이 울리는 시각을 HH:MM형태로 출력합니다.
HH는 00, 01, 02, ..., 23 중에 하나이며, MM은 00, 01, 02, ..., 59 중 하나입니다.
입력 #1
00:00
5
입력 #2
13:49
50
출력 #1
00:10
출력 #2
10:14
18.
준하는 침착해야 할 때 소수를 세는 버릇이 있습니다. 소수는 1과 자기 자신으로만 나누어 떨어지는 고독한 수이기 때문입니다. 오늘도 마음의 안정을 위해 준하는 소수를 2부터 N까지 작은 순으로 칠판에 써 놓았는데, 준하의 친구인 또리가 칠판에서 일부를 지워버렸습니다. 또리가 지워버린 내용은 숫자 전체일 수도, 숫자의 일부일 수도 있습니다. 준하는 N이 무엇이었는지 기억이 나지 않아 초조해하고 있습니다. 준하를 위해 N의 최소값을 계산해주는 프로그램을 작성해 주세요.
예를 들어 1, 2, 3, 4, 5가 칠판에 남아있었다면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53의 소수 중에서 또리가 2, 3, 5, 7은 모두 지워버리고 남은 소수 중에서 서로 다른 십의 자리들에 대해서 각각 한개의 소수만 남기고, 남은 소수 중에서도 십의 자리의 숫자만 남겨놨다고 볼 수 있습니다. 그러므로 N의 최소값은 53이 됩니다. (2, 3, 5, 7), 11, (13, 17, 19), 23, (29), 31, (37), 41, (43, 47), 53과 같이 만들어서 괄호 내의 수를 모두 제거해 11, 23, 31, 41, 53이 남고, 여기서 일의 자리를 모두 제거해 1, 2, 3, 4, 5만 남은 상황을 생각할 수 있습니다.
첫째 줄에 칠판에 남은 숫자의 개수 K가 주어집니다. (1 ≤ K ≤ 100)
이어서 칠판에 남은 숫자 A_i가 공백으로 구분되어 주어집니다. (0 ≤ A_i ≤ 9)
N의 최소값을 출력합니다.
입력 #1
3
2 3 7
입력 #2
5
1 2 3 4 5
출력 #1
7
출력 #2
53
19.
기성이네 회사의 서버실에는 N대의 서로 다른 장치가 있습니다. 각 장치는 RED타입 또는 BLUE타입입니다. 장치들은 여러개의 전선들로 연결되어 있습니다. 전선은 서로 다른 두 장치를 양방향으로 연결합니다. 모든 장치 쌍 N × (N - 1) ÷ 2 가지에 대해 각 쌍을 연결하는 전선은 최대 한개입니다.
뜻밖의 사고로 각 장치가 어떤 타입인지, 전선이 몇 개였는지, 각 전선이 연결하는 장치쌍은 무엇인지에 대한 정보가 모두 유실되었습니다. 남은 정보는 각 장치와 직접 연결되어 있던 RED타입 장치의 수와 BLUE타입 장치의 수 뿐입니다. 여러분은 남은 정보를 모두 만족하도록 장치들의 타입을 결정하고, 전선들로 장치들을 연결해야 합니다.
각 장치의 타입은 임의로 결정해도 좋지만, 전선은 매우 비싸므로 전선의 개수를 최소화하려 합니다. 기성이는 최소한 몇 개의 전선이 필요한지 계산한 다음, 그 개수의 전선을 이용해 장치들을 연결하고 각 장치의 타입을 결정하는 경우의 수를 계산해야 합니다.
첫번째 예시 입력을 1개의 전선으로 충분하다고 가정한 뒤 분석해봅시다. 1번 장치와 2번 장치는 각각 BLUE타입과 RED타입이어야 하며, 서로 연결되어야 합니다. 3번 장치와 4번 장치는 어떤 타입이라도 조건을 만족할 수 있습니다. 총 방법의 수는 (1개의 전선으로 연결할 장치 쌍 1가지) × (3번 장치의 타입 2가지) × (4번 장치의 타입 2가지) = 4가지입니다. 디버깅을 돕기 위해 추가 정보를 제공하자면, 전선 2개로 연결하는 방법은 12가지이고 전선 3개로 연결하는 방법은 8가지입니다.
최소한 몇 개의 전선이 필요한지 계산한 다음, 그 개수의 전선을 이용해 장치들을 연결하고 각 장치의 타입을 결정하는 경우의 수를 출력하는 프로그램을 작성해 주세요.
입력값 설명
첫째 줄에 장치의 수 N이 주어집니다. (2 ≤ N ≤ 5)
다음 N개의 줄에 걸쳐 각 줄에 두 정수 R, B가 공백으로 구분되어 주어집니다. (-1 ≤ R ≤ N - 1, -1 ≤ B ≤ N - 1, R + B ≤ N - 1) 두 정수 R, B는 해당 장치에 연결된 장치의 타입의 개수를 나타냅니다.
R이 0 이상이라면 장치들을 모두 연결하고 난 뒤 해당 장치와 연결된 RED타입 장치의 수는 R개여야 합니다.
R이 -1이라면 정보가 유실된 것으로, 장치들을 모두 연결하고 난 뒤 해당 장치와 연결된 RED타입 장치의 수는 몇 개여도 상관 없습니다.
B가 0 이상이라면 장치들을 모두 연결하고 난 뒤 해당 장치와 연결된 BLUE타입 장치의 수는 B개여야 합니다.
B가 -1이라면 정보가 유실된 것으로, 장치들을 모두 연결하고 난 뒤 해당 장치와 연결된 BLUE타입 장치의 수는 몇 개여도 상관 없습니다.
전선을 하나도 사용하지 않고 위 조건을 모두 만족할 수 있는 경우는 입력으로 주어지지 않습니다.
출력값 설명
입력에서 주어진 조건을 만족하도록 장치들을 연결할 수 없다면 -1을 출력합니다.
입력에서 주어진 조건을 만족하도록 장치들을 연결할 수 있다면 다음과 같이 출력합니다.
첫째 줄에 전선이 최소 몇 개 필요한지 출력합니다.
둘째 줄에 그러한 개수의 전선으로 입력에서 주어진 조건을 만족하도록 장치들의 타입을 결정하고, 전선들로 장치들을 연결하는 방법이 몇 가지인지 출력합니다.
입력 #1
4
1 0
0 1
-1 -1
-1 -1
입력 #2
2
1 0
0 0
출력 #1
1
4
출력 #2
-1
20.
기성이는 온라인 커뮤니티를 운영하는 회사의 게시판 관리자입니다. 그의 주요 업무는 불필요한 게시글(광고 게시글, 도배성 게시글 등)을 삭제하는 것입니다. 기성이가 열심히 일한 결과, 커뮤니티의 평판이 좋아져 수많은 신규 사용자를 유치하는데 성공하였습니다. 하지만 커뮤니티의 성장에 따른 부작용으로 광고성 게시글과 악성 사용자들이 크게 늘어났습니다.
광고성 게시글 들은 대부분 동일한 제목과 내용으로 등록되기 때문에, 광고 차단 필터를 이용해 대응할 수 있었습니다. 어떤 문장을 광고 차단 필터에 등록하면, 필터에 등록된 문장을 제목으로 사용하는 게시글은 게시판에 노출되지 않습니다. 문장이란 여러 단어들 사이에 공백을 하나씩 두고 나열한 것이고, 단어는 하나 이상의 영어 알파벳 소문자들을 공백 없이 이어붙인 것입니다. 예를 들어 세 단어 buy, our, merch로 문장 buy our merch를 만들 수 있습니다.
악성 사용자는 재미를 위해 광고 차단 필터에 등록된 문장의 두 단어를 골라 자리를 바꾼 것을 제목으로 하는 게시글들을 작성합니다. 문장 buy our merch에 광고 차단 필터가 적용되었다면, 악성 사용자는 merch our buy, buy merch our등의 문장을 제목으로 사용합니다. 하지만, our merch buy는 어떤 두 단어의 자리를 바꾸어도 buy our merch가 되지 못하므로 제목으로 사용하지 않습니다.
그런데 아뿔싸, 불의의 사고로 광고 차단 필터가 초기화 되었습니다. 기성이는 만약 악성 사용자가 제목으로 사용한 문장들을 이용해 광고성 게시글의 제목을 복원할 수 있다면 필터를 복구하는데 도움이 될 것이라 생각합니다. 악성 사용자가 제목으로 사용한 서로 다른 두 개의 문장을 이용할 것인데, 적어도 둘의 길이가 같으며 한 쪽에서 등장한 단어는 반드시 다른 쪽에서도 등장해야 도움이 됨을 알 수 있습니다.
악성 사용자가 제목으로 사용한 서로 다른 두 개의 문장이 입력으로 주어집니다. 두 문장의 길이는 같으며, 한 쪽에서 등장한 단어는 반드시 다른 쪽에서도 등장합니다. 문제의 상황을 단순하게 만들기 위해 한 문장에 같은 단어가 여러번 등장하는 경우는 주어지지 않습니다. 두 단어의 자리를 바꾸면 주어진 두 개의 문장을 모두 만들 수 있는 문장이 몇개인지 출력하는 프로그램을 작성해 주세요.
첫째 줄에 악성 사용자가 제목으로 사용한 문장에 등장하는 단어의 수 N이 주어집니다. (3 ≤ N ≤ 5,000)
둘째 줄에 악성 사용자가 제목으로 사용한 첫번째 문장이 주어집니다.
셋째 줄에 악성 사용자가 제목으로 사용한 두번째 문장이 주어집니다.
모든 단어의 길이는 1 이상 5 이하입니다.
문제의 정답을 출력합니다.
입력 #1
3
merch our buy
buy merch our
입력 #2
6
wel come to aivle sch ool
wel come aivle to sch ool
출력 #1
3
출력 #2
0
21.
기성이는 다양한 종류의 스위치를 생산하는 공장을 운영하고 있습니다. 기성이의 공장에서 생산된 스위치들은 튼튼한 내구성과 훌륭한 품질로 유명합니다. 스위치의 상태는 0(꺼짐) 또는 1(켜짐) 두 가지입니다.
가장 많이 팔리는 스위치는 "토글 스위치"와 "홀드 스위치"입니다. 토글 스위치는 누르는 순간마다 상태가 반전됩니다. 상태를 한번 더 반전시키려면 우선 손을 뗐다가 다시 눌러야 합니다. 홀드 스위치는 누르고 있는 동안 켜짐 상태이고, 떼면 꺼짐 상태입니다.
기성이는 스위치에 대한 연구 자료를 작성하기 위해 실험을 했습니다. 실험은 토글 스위치를 꺼짐 상태로 두고, 왼손과 오른손을 모두 스위치에서 뗀 채로 시작합니다. 실험에서 할 수 있는 행동은 다음과 같은 4가지입니다.
A. 왼손으로 토글 스위치를 누르고 유지한다.
B. 토글 스위치에서 왼손을 뗀다.
C. 오른손으로 홀드 스위치를 누르고 유지한다.
D. 홀드 스위치에서 오른손을 뗀다.
실험 기록지에는 기성이의 행동이 (행동한 시각) (행동의 종류) 형식으로 기록되어 있습니다. 예를 들어 실험을 시작하고 정확히 3초 뒤 A 행동을 하고 정확히 5초 뒤에는 B 행동을 했을 때의 기록지는 다음 [기록지]와 같습니다.
[기록지]
3 A
5 B
기성이는 실험을 시작하고 정확히 k초(1 ≤ k ≤ 1,000,000)가 지났을 때, 각 스위치가 몇 초동안 켜져 있었을지 궁금합니다. 기록지가 위 [기록지]와 같고 k = 6인 경우를 예로 들어봅시다. 토글 스위치는 3초가 되는 순간 켜진 뒤 다시 꺼지지 않으므로 답은 3(3초 ~ 4초, 4초 ~ 5초, 5초 ~ 6초)입니다. 홀드 스위치는 실험 내내 꺼져있으므로 답은 0입니다. 실험 기록지가 주어지면 기성이의 의문을 여러 번 해결하는 프로그램을 작성해 주세요.
[ 입력값 설명 ]
첫째 줄에 기록지에 적힌 행동의 수 N이 주어집니다. (1 ≤ N ≤ 1,000)
다음 N개의 줄에 걸쳐 각 줄에 정수 T와 문자 O가 공백으로 구분되어 주어집니다. (1 ≤ T ≤ 1,000,000, O는 'A', 'B', 'C', 'D'중 하나)
T는 행동한 시각을, O는 지문에서 설명한 행동의 종류를 의미합니다.
기록은 행동한 시각의 오름차순으로 주어집니다.
누르고 있는 중인 버튼을 또 누르거나, 누르지 않고 있는 버튼에서 손을 떼는 기록은 주어지지 않습니다.
N + 2번째 줄에 기성이가 가진 의문의 개수 Q가 주어집니다. (1 ≤ Q ≤ 1,000)
다음 Q개의 줄에 걸쳐 각 줄에 정수 k가 주어집니다.
각 k는 의문 실험을 시작하고 정확히 k초(1 ≤ k ≤ 1,000,000)가 지났을 때, 각 스위치는 몇 초 동안 켜져 있었을까요?에 대응합니다.
입력으로 주어지는 모든 시각(T와 k)은 서로 다릅니다.
[출력값 설명]
총 Q개의 줄을 출력합니다.
각 줄에는 기성이의 의문에 대해 토글 스위치가 켜져 있었던 시간, 홀드 스위치가 켜져 있었던 시간을 공백으로 구분해 출력합니다.
정답의 순서는 입력에서 의문이 주어진 순서와 같아야 합니다.
입력 #1
2
3 A
5 B
4
4
6
8
10
입력 #2
6
1 A
2 C
3 D
4 C
5 D
6 C
1
7
출력 #1
1 0
3 0
5 0
7 0
출력 #2
6 3
22.
농부 기성이는 2차원 평지에 N마리의 닭을 자연 방목하고 있습니다. 넓은 땅에서 뛰어놀며 자란 닭들은 매우 건강하며 훌륭한 품질의 달걀을 낳습니다. 평지에는 N그루 이상의 나무들이 격자점(x좌표와 y좌표가 모두 정수인 점)에 뿌리내리고 있습니다. 동물 복지에 진심인 기성이는 모든 닭은 서로 다른 나무를 좋아한다는 사실을 관찰했습니다. 이 문제에선 앞으로 닭이 좋아하는 어떤 나무가 있다면 그 나무를 닭나무라고 합시다.
어느 날 들개가 인근 농장을 습격해 많은 닭들이 죽었습니다. 큰 충격을 받은 기성이는 들개가 자신의 농장도 습격하기 전 방목지에 울타리를 설치하려고 합니다. 울타리는 네 변이 모두 x축 또는 y축과 평행하며 네 꼭지점이 모두 격자점인 직사각형입니다. 설치 비용은 직사각형의 네 변의 길이의 합과 같습니다.
기성이는 농장 전체를 울타리로 둘러싸고 싶었지만 예산 문제에 부딪히고 말았습니다. 절충안으로 최대한 많은 닭나무를 포함하도록 울타리를 설치하기로 했습니다. 울타리의 변 위에 있는 나무는 울타리에 포함된 것으로 인정하지 않습니다. 포함할 닭나무의 수가 N - 4, N - 3, N - 2, N - 1, N개인 다섯가지 경우에 대해 기성이의 절충안에 따른 울타리의 설치 비용을 출력하는 프로그램을 작성해 주세요.
첫째 줄에 닭의 수 N이 주어집니다. (5 ≤ N ≤ 55)
다음 N개의 줄에 걸쳐 각 닭나무의 x좌표와 y좌표가 공백으로 구분되어 주어집니다. (0 ≤ 모든 좌표의 절댓값 ≤ 100,000,000)
총 5개의 줄을 출력합니다.
i번째 줄에는 울타리에 포함할 닭나무의 수가 N - (i - 1)그루일 때 기성이의 절충안에 따른 울타리의 설치 비용을 출력합니다.
입력 #1
5
1 0
1 -400
1 200
1 -200
1 400
입력 #2
6
4 4
5 6
7 5
11 13
12 15
17 10
출력 #1
1608
1208
808
408
8
출력 #2
56
46
40
18
14
23.
토끼와 거북이는 수천년째 달리기 시합을 하고 있습니다. 어느덧 시간이 흘러 21세기가 되었고, 토끼와 거북이의 달리기를 학습한 인공지능 모델이 등장했습니다. 두 가상 동물은 2차원 메타버스 세계에서 달리기 시합을 하게 되었습니다.
달리기 시합의 승자는 미로의 맨 위 왼쪽 칸(1행 1열)에서 출발해 미로의 맨 아래 오른쪽 칸(N행 M열)에 먼저 도착하는 쪽입니다. 미로의 각 칸은 벽 또는 빈 칸으로, 토끼와 거북이 모두 벽을 넘거나 부술 수 없습니다. 미로의 테두리(1행의 위, N행의 아래, 1열의 왼쪽, M열의 오른쪽)는 모두 벽으로 막혀 있습니다.
토끼는 1분에 한 번 상하좌우 중 한 방향으로 최대 2칸 이동합니다. 토끼의 이동을 조금 더 자세하게 서술하겠습니다. 우선 이동할 방향을 정하고, 1칸 이동합니다. 같은 방향으로 1칸 더 이동할 수 있다면 반드시 이동해야 하며, 아니라면 거기서 멈춥니다. 첫 번째 예시 입력을 예로 들면, 토끼 로봇이 오른쪽 - 아래 - 오른쪽 순으로 이동할 때 그의 위치는 1행 1열 - 1행 2열 - 3행 2열 - 3행 4열 순입니다.
미로의 모습이 입력으로 주어집니다. 토끼가 미로의 맨 위 왼쪽 칸에서 출발해 미로의 맨 아래 오른쪽 칸으로 이동하는데 적어도 몇 분이 걸리는지 출력하는 프로그램을 작성하세요.
첫째 줄에 미로의 세로 너비 N과 가로 너비 M이 주어집니다. (2 ≤ N ≤ 50, 2 ≤ M ≤ 50)
둘째 줄부터 N개의 줄에 걸쳐 미로의 정보가 주어집니다. #는 벽을 나타내며, .는 빈 칸을 나타냅니다.
토끼가 미로의 맨 위 왼쪽 칸에서 출발해 미로의 맨 아래 오른쪽 칸으로 이동하는데 몇 분이 걸리는지 출력합니다.
어떻게 이동해도 맨 아래 오른쪽 칸에 도달하지 못한다면 대신 -1을 출력합니다.
입력 #1
3 4
..##
#.##
....
입력 #2
5 4
....
#.##
..#.
....
..#.
출력 #1
3
출력 #2
-1
24.
어느 날 기승이가 종이 한장과 주사위 3개를 가져와 기성이에게 게임을 제안했습니다. 주사위는 우리가 일반적으로 알고있는 각 면에 1 이상 6 이하의 서로 다른 정수가 적힌 정육면체입니다. 주사위를 굴리면 1 이상 6 이하의 정수를 각각 1/6의 동일한 확률로 얻을 수 있습니다. 종이에는 N개의 수가 일렬로 적혀있으며, 모든 수는 -100 이상 100 이하의 정수입니다.
기성이는 정수 K를 하나 고른 뒤 주사위 3개를 굴립니다. 세 주사위의 눈의 합을 T라고 할 때, 기성이의 점수는 종이에 K + T번째로 적힌 수와 같습니다. 만약 K + T가 N보다 크다면 기성이의 점수는 -100점입니다.
기승이도 위와 똑같은 시행을 하여 점수가 높은 사람이 게임에서 이깁니다. 승부욕이 발동한 기성이는 어떤 K를 골라야 점수의 기댓값이 최대가 되는지 구하려고 합니다. 기성이를 위해 어떤 K를 골라야 점수의 기댓값이 최대가 되는지 출력하는 프로그램을 작성해 주세요.
첫째 줄에 N이 주어집니다. (1 ≤ N ≤ 10,000)
둘째 줄에 종이에 적힌 N개의 정수가 공백으로 구분되어 주어집니다. (-100 ≤ 종이에 적힌 수 ≤ 100)
i번째 수는 종이에 i번째로 적힌 수와 같습니다.
첫째 줄에 점수의 최대 기댓값에 216을 곱해 출력합니다.
기댓값에 216을 곱하면 정수가 됨을 증명할 수 있습니다.
둘째 줄에 점수의 최대 기댓값을 얻기 위해 고를 수 있는 K를 오름차순으로 모두 출력합니다.
입력 #1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
입력 #2
25
48 3 39 8 98 38 5 9 83 89 4 8 9 3 9 48 90 88 100 76 5 50 77 23 67
출력 #1
216
1 2
출력 #2
12345
8
25.
격투기, 씨름 등 대결 스포츠에 관심이 있다면 체급이라는 말을 들어보았을 것입니다. 일반적으로 두 선수의 몸무게 차이가 크다면 체급 차이가 크다고 합니다. 두 선수의 실력이 비슷하다면 몸무게가 높은 사람이 압도적으로 유리하기 때문에, 대결 스포츠는 보통 몸무게가 비슷한 선수들끼리 대결합니다.
기성 씨름단에는 1번부터 N번까지의 번호가 있는 N명의 씨름 선수가 있습니다. i번 선수는 몸무게가 w[i]이고, p[i]개의 걱정거리가 있습니다. 각 선수는 어떤 선수의 몸무게가 (자신의 몸무게) - (자신의 걱정거리의 수)보다 작다면 그 선수를 상대로 승리를 확신합니다. 모든 선수의 몸무게와 걱정거리의 수가 주어지면, 각 선수가 승리를 확신하는 다른 선수는 몇 명인지 출력하는 프로그램을 작성해 주세요.
입력값 설명
첫째 줄에 선수의 수 N이 주어집니다. (3 ≤ N ≤ 50,000)
둘째 줄에 w[1]과 p[1]이 공백으로 구분되어 주어집니다. (1 ≤ w[1] ≤ 100,000, 1 ≤ p[1] ≤ 100,000)
셋째 줄에 두 정수 multiplier_w, multiplier_p가 공백으로 구분되어 주어집니다. (1 ≤ multiplier_w ≤ 100,000, 1 ≤ multiplier_p ≤ 100,000)
넷째 줄에 갱신 정보(갱신 정보가 무엇인지는 후술)가 몇 개인지를 뜻하는 정수 K가 주어집니다. (0 ≤ K ≤ 50)
다음 K개의 줄에 걸쳐 각 줄에 하나의 갱신 정보를 구성하는 세 정수 u1, u2, u3 가 공백으로 구분되어 주어집니다. (2 ≤ u1 ≤ N - 1, 1 ≤ u2 ≤ 100,000, 1 ≤ u3 ≤ 100,000, 모든 갱신 정보의 u1은 서로 다르다.)
i번 선수의 몸무게와 걱정거리의 수는 다음 과정을 순서대로 시행하여 알 수 있습니다. (2 ≤ i ≤ N)
단, 2번 선수부터 N번 선수까지 번호의 오름차순으로 계산해야 합니다.
1.
i번 선수의 몸무게는 i-1번 선수의 몸무게에 multiplier_w를 곱한 뒤 1,000,000,007로 나눈 나머지입니다.
2.
i번 선수의 걱정거리의 수는 i-1번 선수의 걱정거리의 수에 multiplier_p를 곱한 뒤 1,000,000,007로 나눈 나머지입니다.
3.
u1이 i와 같은 갱신 정보가 있다면, multiplier_w와 multiplier_p를 해당 갱신 정보의 u2와 u3으로 교체합니다.
첫번째 예시 입력의 선수들은 각각 몸무게가 1000, 2000, 6000이고, 걱정거리의 수는 10, 300, 2700입니다.
위 과정을 올바르게 시행한다면 몸무게가 0인 선수나 걱정거리가 0개인 선수가 절대 존재하지 않습니다.
A[i]가 i번 선수가 승리를 확신하는 다른 선수의 수라고 할 때, (A[1] + A[2] + … + A[N-1] + A[N])을 1,000,000,007로 나눈 나머지를 출력합니다.
입력 #1
3
1000 10
2 30
1
2 3 9
입력 #2
6
41707 37045
72490 45229
2
2 85276 41719
3 55857 73979
출력 #1
3
출력 #2
3
26.
1부터 N까지의 자연수로 이루어진 순열이 있습니다. 이 순열의 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열입니다.
예를 들어 N이 3인 경우 사전 순으로 나열하면 다음과 같습니다.
1 2 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
이때 순열 (2 3 1)의 사전 순으로 다음 순열은 (3 1 2) 입니다.
또한 순열 (2 3 1)의 사전 순으로 2번째 다음 순열은 (3 2 1)입니다.
대희는 "대희식 순서"를 만들었습니다. "대희식 순서"란 사전식 순서를 따르면서 다음 규칙 하나를 추가한 것입니다.
사전 순으로 가장 마지막 순열의 다음 순열은 사전 순으로 가장 앞서는 순열이다.
예를 들어 N이 3인 경우
순열 (3 1 2)의 대희식으로 다음 순열은 (3 2 1) 입니다.
순열 (3 1 2)의 대희식으로 2번째 다음 순열은 (1 2 3)입니다.
어떤 순열이 주어질 때 대희식으로 K번째 다음 순열을 출력하는 프로그램을 작성해 주세요.
첫째 줄에 자연수 N과 K가 공백으로 구분되어 주어집니다.(2 ≤ N, K ≤ 1,000)
둘째 줄에 순열이 공백으로 구분되어 주어집니다.
어떤 순열이 주어질 때 대희식으로 K번째 다음 순열을 공백으로 구분하여 출력하세요.
입력 #1
3 1
3 2 1
입력 #2
4 24
1 2 3 4
출력 #1
1 2 3
출력 #2
1 2 3 4
27.
동욱이는 N×M 격자판 미로를 탈출하려고 합니다. 동욱이는 미로를 상하좌우로 한 칸씩 움직입니다. 이때 벽이 없는 칸으로만 이동할 수 있습니다.
미로에는 꿀열매라는 것이 있습니다. 꿀열매를 먹으면 동욱이가 하루 동안 움직일 수 있는 칸의 수가 1 증가합니다. 꿀열매를 먹지 않은 상태의 동욱이는 하루에 한 칸씩 움직일 수 있습니다. 꿀열매는 여러 번 먹어도 효과가 중첩되지 않습니다.
집이 그리운 동욱이는 최적의 방법으로 미로를 탈출합니다. 동욱이가 미로를 탈출하는 데 며칠이 걸리는지 출력하는 프로그램을 작성해 주세요.
첫째 줄에 자연수 N과 M이 공백으로 구분되어 주어집니다. (2 ≤ N, M ≤ 100)
둘째 줄부터 N개의 줄에 걸쳐 미로의 상태가 주어집니다. 미로는 #, G, E 하나의 A, 하나의 B로만 구성되어 있으며 각각의 문자가 의미하는 것을 다음과 같습니다.
#: 벽
G: 꿀열매
E: 빈 공간
A: 동욱이의 위치
B: 출구
입력으로는 탈출할 수 있는 경우만 주어집니다.
동욱이가 미로를 탈출하는데 며칠이 걸리는지 출력하세요.
입력 #1
1 3
AEB
입력 #2
1 7
AGGEEEB
출력 #1
2
출력 #2
4
28.
민규는 화장실 바닥을 바라보고 있었습니다. 바닥은 격자판 모양이었고, 계속해서 바라보다 보니 이런 생각이 들었습니다.
세로 크기가 N이고, 가로 크기가 M인 격자판을 이웃한 격자는 같은 색으로 칠하지 않으면서 서로 다른 세 가지 색으로 칠하면 칠할 수 있는 경우의 수는 몇 개가 될까?
이때 이웃한 격자란 한 변을 공유하는 두 격자를 의미합니다.
격자의 크기가 주어질 때, 이웃한 격자는 같은 색으로 칠하지 않으면서 격자를 서로 다른 세 가지 색으로 칠할 수 있는 경우의 수를 출력하는 프로그램을 작성해 주세요.
첫째 줄에 자연수 N, M이 공백으로 구분되어 주어집니다.(1 ≤ N, M ≤ 5)
이웃한 격자는 같은 색으로 칠하지 않으면서 격자를 서로 다른 네 가지 색으로 칠할 수 있는 경우의 수를 출력하세요.
입력 #1
2 2
입력 #2
2 3
출력 #1
18
출력 #2
54
29.
철수는 회사 연구실에서 근무 중입니다. 연구실에는 N개의 용액이 존재합니다. 각 용액은 A 타입, B 타입, C 타입 중 하나입니다. 현재 철수는 세 가지 타입의 용액을 섞어 신소재를 개발할 수 있는지 실험하고 있습니다.
실험 과정은 다음과 같습니다.
1.
실험 시작 시, 비커는 비어있습니다.
2.
용액 한 개를 선택해 비커에 모두 투입합니다.
3.
N개의 용액을 모두 소모하면 실험이 종료됩니다.
간단한 실험이지만 주의해야 할 사항이 있습니다. 직전에 투입한 용액과 같은 타입의 용액을 연속해서 투입하면 사고가 발생합니다.
예를 들어 비커에 첫 번째로 투입한 용액이 A 타입이라고 가정하겠습니다. 두 번째로 투입하는 용액이 A 타입이라면 사고가 발생합니다. 두 번째로 투입하는 용액이 B 타입 또는 C 타입일 경우 사고가 발생하지 않습니다.
각 타입의 용액의 개수가 주어졌을 때, 철수가 사고 발생 없이 실험을 끝마칠 수 있는지 여부를 구하는 프로그램을 작성해주세요.
첫째 줄에 양의 정수 A, B, C가 공백으로 구분되어 주어집니다. 이는 각 타입 용액의 개수를 의미합니다. (1 ≤ A, B, C ≤ 10,000)
첫째 줄에 사고 발생 없이 실험을 끝마칠 수 있으면 "YES"를, 그렇지 않으면 "NO"를 출력합니다. (큰 따옴표 제외)
입력 #1
1 2 1
입력 #2
2 1 5
출력 #1
YES
출력 #2
NO
30.
철수는 집에서 조카를 돌봐주고 있습니다. 조카는 N개의 막대를 가지고 놀고있습니다. 각 막대에는 1번부터 N번까지 번호가 붙어있습니다. i번 막대의 길이는 a_i로 표기됩니다.
조카는 임의의 막대 세 개를 사용해 삼각형을 만드는데, 어떤 경우에는 삼각형이 제대로 만들어지지만 막대들의 길이에 따라 삼각형이 만들어지지 않는 경우도 존재합니다. 이는 가장 긴 변의 길이가 다른 두 변의 길이의 합보다 작아야 삼각형을 만들 수 있다는 조건 때문입니다.
철수는 조카가 어떤 세 막대를 선택해도 삼각형을 만들 수 있도록 0개 이상의 막대를 버리려고 합니다.
예를 들어 N = 5, 각 막대의 길이가 1, 3, 2, 4, 3이라고 가정하겠습니다. 조카가 1번, 2번, 4번 막대를 선택할 경우, a_1 + a_2 = a_4가 되어 삼각형을 만들 수 없습니다. 1번 막대를 버리고 나면, 2번 ~ 4번 막대 중 어떤 세 막대를 선택해도 삼각형을 만들 수 있습니다.
철수는 가능한 많은 막대를 남기고 싶습니다. 철수가 남길 수 있는 막대의 최대 개수를 구하는 프로그램을 작성해주세요.
첫째 줄에 막대의 개수 N이 주어집니다. (3 ≤ N ≤ 100)
둘째 줄에 i번 막대의 길이 a_i가 공백으로 구분되어 주어집니다. a_i는 정수입니다. (1 ≤ a_i ≤ 1,000,000)
반드시 1개 이상의 삼각형을 만들 수 있는 입력만 주어집니다.
첫째 줄에 남길 수 있는 막대의 최대 개수를 출력합니다.
입력 #1
5
1 3 2 4 3
입력 #2
3
4 2 5
출력 #1
4
출력 #2
3