Homile

문제

품질이냐 가격이냐, 그것이 문제로다..

진주 나들이를 온 보선이는 기념품으로 촉석루 미니어처를 사기로 했다. 촉석루는 진주성에 있는 누각이며 경상남도 유형문화재 중 하나로, 진주성의 남쪽 지휘대로 사용됨과 동시에 논개가 촉석루 앞 의암에서 순국한 것으로 알려져 유명한 곳이다.

촉석루 미니어처를 사기 위해 기념품 가게에 들른 보선이는 놀라움을 금치 못했다. 왜냐하면, 가게에는 각양각색의 촉석루 미니어처가 진열되어 있었기 때문이다. 그리고 모든 촉석루 미니어처는 장인이 한 땀 한 땀 심혈을 기울여서 만들어서 그런지 품질과 가격이 천차만별이었고, 품질과 가격이 전부 동일한 두 촉석루 미니어처는 없었다. 각양각색의 촉석루 미니어처를 본 보선이는 물욕이 폭발할 뻔했지만 가까스로 마음을 진정시키고, 촉석루 미니어처를 두 개만 사기로 했다. 보선이는 두 가지 방법으로 촉석루 미니어처를 골라보기로 했는데, 이는 다음과 같다.

• 진열되어 있는 촉석루 미니어처 중에서 품질이 가장 높은 촉석루 미니어처를 골라 가져온다. 만약 그런 미니어처가 여러 개라면 가격이 가장 낮은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 첫 번째 방법이다.
• 진열되어 있는 촉석루 미니어처 중에서 가격이 가장 낮은 촉석루 미니어처를 골라 가져온다. 만약 그런 미니어처가 여러 개라면 품질이 가장 높은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 두 번째 방법이다.

보선이가 각 방법에 따라 촉석루 미니어처들을 고르게 될 때 어떤 촉석루 미니어처들을 고르게 되는지 알아보자.

입력

첫 번째 줄에는 기념품 가게에 진열되어 있는 촉석루 미니어처의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)

두 번째 줄부터 N개의 줄에 걸쳐 가게에 진열되어 있는 i번째 촉석루 미니어처 종류의 품질 Q_i, 가격 P_i가 공백으로 구분되어 주어진다. (1≤Q_i,P_i≤10000)입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에는 첫 번째 방법을 선택했을 때의 첫 번째로 고른 촉석루 미니어처의 품질과 가격, 두 번째로 고른 촉석루 미니어처의 품질과 가격을 공백으로 구분하여 순서대로 출력한다.

두 번째 줄에는 두 번째 방법을 선택했을 때의 첫 번째로 고른 촉석루 미니어처의 품질과 가격, 두 번째로 고른 촉석루 미니어처의 품질과 가격을 공백으로 구분하여 순서대로 출력한다.

첫 번째 방법의 결과가 두 번째 방법의 결과에 영향을 미치지 않는다.

문제

시현이 카페에 양갈래 손님들이 들어가려고 한다.

양갈래 손님들은 양갈래를 너무 좋아하는 나머지 두 명씩 모여 있어 총 인원은 짝수이다.

시현이 카페에는 두 명씩 앉을 수 있는 테이블이 충분히 많이 있고, 양갈래 손님들은 한 테이블에 두 명씩 앉기로 하였다.

그런 양갈래 손님들을 맞이하게 된 시현이는 갑자기 궁금증이 생겼다.

손님들이 앉는 경우의 수를 세는 조건이 다음과 같을 때, 양갈래 손님들이 모두 앉을 수 있는 방법의 수는 몇 가지가 있을까?

1. 테이블의 좌석을 구분하지 않는다.
   • 한 테이블에서 손님 A와 손님 B가 앉는 경우, 손님 B와 손님 A가 앉는 경우는 같은 경우이다.
2. 각각의 테이블 또한 구분하지 않는다.
   • 1번 테이블에 손님 A, B가 앉고, 2번 테이블에 손님 C, D가 앉는 것과, 1번 테이블에 손님 C, D가 앉고, 2번 테이블에 손님 A, B가 앉는 것은 서로 같은 경우이다.

입력

첫째 줄에 양갈래 손님의 수 �$N$이 주어진다. (2≤�≤28$2 \leq N \leq 28$, �$N$은 짝수)

출력

첫째 줄에 양갈래 손님들이 앉을 수 있는 경우의 수를 출력한다.

연산 중 32비트 정수형 타입의 표현 범위를 초과할 수 있으므로 오버플로우에 주의한다.

4

3

문제풀이(1)

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());

let result = 1;

for (let i = N; i > 0; i -= 2) {
  result *= (i * (i - 1)) / 2;
  result /= i / 2;
}

console.log(result);

문제

심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다.

(()(()))()()

그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다.

(()    ((    )))()    ()

크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.

)))()

승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다.

((()))()

그러나 괄호열을 사서 붙이는 데에는 돈이 들고 많이 붙일수록 놀기가 불편해지기 때문에, 승현이는 가능한 한 괄호열을 적게 추가하려고 합니다.

승현이가 망가뜨리고 사용 가능한 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다.

출력

첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.

)(()

2

문제풀이(1)

문제

키보드에서 어떤 키를 누르면 어떤 키가 눌러졌는지 컴퓨터에 전송되고, 컴퓨터에서는 키가 눌러진 순서대로 화면에 출력된다.

승지는 팀 과제로 보고서 100장을 작성해야 하는 데, 마감 시간이 얼마 남지 않아서 팀원에게 도움을 요청하였다. 하지만 컴퓨터가 하나뿐이라 보고서를 동시에 작성할 수 없었다.

주변을 둘러보니 쓰지 않는 키보드 여러 개가 바닥에서 굴러다니는 것을 보았다. 급한 대로 컴퓨터에 키보드 여러 개를 연결해서 타자 속도를 올리기로 했다.

문제는 원하는 문장을 작성하기 위해서는 서로 호흡을 잘 맞춰야 하는데, 키보드의 동작 원리를 아직 알지 못했던 승지는 어떤 결과가 출력될지 알 수 없었다.

승지는 팀원 N명에게 N개의 키보드를 나눠주고 전부 컴퓨터에 연결했다. 각자 어느 시간에 어떤 키를 누를지를 미리 정한다면, 어떤 결과가 화면에 출력될 것인지 알아내고자 한다.

키보드의 번호는 컴퓨터에 연결된 순서대로 1번 키보드, 2번 키보드, .... N번 키보드이다. 동시에 여러 키보드에서 키를 누른다면 번호가 작은 키보드에서 누른 키가 먼저 출력되지만, 하나의 키보드에서 여러 개의 키를 동시에 누를 수는 없다. 즉, 하나의 키보드에서 각 키를 누른 시간은 모두 다르다.

입력

첫째 줄에 연결된 키보드의 개수 N과, 키보드를 누르게 될 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

다음 M개의 줄에 정수 a, b와 문자 c가 주어진다. 이는 a번 키보드로, b초에 문자 c가 적힌 키를 누를 것이라는 의미이다. (1 ≤ a ≤ N, 0 ≤ b ≤ 1,000,000)

키보드에는 알파벳 대문자와 숫자키만 존재한다.

출력

모든 입력이 끝난 후에 화면에 출력될 결과를 출력한다.

문제

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다. 마술을 하는 순서는 다음과 같다.

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다. 카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

4

2 1 4 3

문제풀이(1)

문제에 나와있는 방식을 반대로 진행하면 초기 카드의 세팅값을 찾을 수 있다.
1. N 번 카드가 있다. (N = 4)
2. N - 1, N번의 카드가 있다. 가장 뒤에 있는 카드를 가장 앞으로 옮긴다.(N회 반복)
   [3, 4] -> [4, 3] -> [3, 4] -> [4, 3]
3. [4, 3]의 카드 배열에 N - 2를 맨 앞에 추가한다. 가장 뒤에 있는 카드를 가장 앞으로 옮긴다.(N - 1회 반복)
   [2, 4, 3] -> [3, 2, 4] -> [4, 3, 2]
4. [4, 3, 2]의 카드 배열에 N - 3을 맨 앞에 추가한다. 가장 뒤에 있는 카드를 가장 앞으로 옮긴다.(N - 2회 반복)
   [1, 4, 3, 2] -> [2, 1, 4, 3]
5. 마지막으로 추가된 배열[2, 1, 4, 3]을 출력한다.

문제

영식이는 민식이와 함게 고속버스를 타고 캠프를 가야 하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.

영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 시각이 특점 시점을 기준으로 10분 후이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.

영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 기다려야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각 Si, 간격 Ii, 대수 Ci가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 영식이가 기다려야 하는 시간을 출력한다. 영식이가 도착하는 동시에 버스가 출발하면 정답은 0이다. 만약 버스가 없어서 캠프에 갈 수 없으면 -1을 출력한다. 정답은 231보다 작다.

제한

• 1 ≤ N ≤ 50
• 1 ≤ T ≤ 1,000,000
• 1 ≤ Si ≤ 1,000,000
• 1 ≤ Ii ≤ 10,000
• 1 ≤ Ci ≤ 100