으하하 공부일기

[문제] 오훈이에게는 지렁이 친구 N마리가 있다. 오훈이는 지렁이들을 위해 소개팅을 주선하고자 한다. 주선 방법은 임의의 지렁이 두 마리를 매칭시킨 후 한 지렁이에게 다른 지렁이가 있는 곳으로 가도록 하는 것이다. 이 때, 수학을 좋아하는 오훈이는 가능한 지렁이들이 움직인 벡터 합의 크기가 작기를 바란다. 지렁이들은 2차원 평면 안에서 꿈틀거리고 있는데, 지렁이들이 움직인 벡터를 나타내는 방법은 점 A 위에 있는 지렁이가 점 B 위에 있는 지렁이에게 갔다면, 그 벡터는 점 A에서 점 B를 가리키는 벡터가 된다. 벡터 V=(x, y)의 크기는 다음과 같이 정의하자. │V│=│(x, y)│= x * x + y * y 모든 지렁이들을 매칭시키고 소개팅을 주선하되, 각 지렁이들이 움직인 벡터를 합하여 그 크기가..

[문제] 승현이는 N(2 ≤ N ≤ 10) 진법의 수 X(1 ≤ X ≤ N10,000,000) 를 공책에 적었다. 승현이는 손이 점점 아프기 시작했고, 머릿속에서 문득 X를 (N-1)로 나눈 나머지가 궁금해졌다. 승현이를 도와 N진법의 수 X가 주어졌을 때에 X를 (N-1)로 나눈 나머지를 계산하는 프로그램을 작성하라. 예를 들면, 9진법의 수 234는 10진법으로 193이고, 8로 나눈 나머지는 1이 된다. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N, X가 공백 하나로 구분되어 주어진다. X가 매우 큰 숫자임에 유의하라. [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, N진법의 수 X..

[문제] 준홍이에게는 카드 두 세트가 있다. 각 카드 세트는 1번 카드부터 N번 카드, 1번 카드부터 M번 카드로 구성되어 있다. 심심했던 준홍이는 각 카드 세트에서 카드 한 장씩을 골랐다. 그리고 각 카드에 적힌 숫자를 더해보았다. 1번 카드와 1번 카드를 골랐다면 카드에 적힌 숫자의 합은 2가 될 것이고, N번 카드와 M번 카드를 골랐다면 카드에 적힌 숫자의 합은 N+M이 될 것이다. 문득 준홍이는 각 카드 세트에서 카드를 한 장씩 골라서 카드에 적힌 숫자를 합한 결과 중, 등장할 확률이 가장 높은 숫자는 어떤 숫자일지 궁금해졌다. 단, 카드 세트에서 어떤 카드를 선택할 확률은 모두 동일하다고 가정한다. 이를 계산하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각..

[문제] 매번 혼자서 알고리즘 문제를 풀던 은기와 자영이는, 많은 사람들의 즐거움을 주기 위해 프로그래밍 대회를 개최하려고 한다. 은기와 자영이는 대회에 사용할 문제를 준비하는 과정에서 문제 제목을 정하게 되었다. 은기는 대회의 문제들에 사용할 수 있는 제목을 N개 만들었다. 자영이는 제목의 가장 앞 글자에 알파벳 대문자 A부터 시작하여, A, B, C, … , Z가 순서대로 한 번씩 등장하면 좋겠다고 하였다. 만약 도중에 특정 알파벳이 문제 제목의 맨 앞 글자로 등장하지 않으면 그 이후의 알파벳은 사용하지 않는다. 예를 들어, 문제 제목으로 Air, Dad, Ear, Blue, Ace가 있다면, A와 B는 등장하였지만, C는 등장하지 않았기 때문에 최대 2개의 문제 제목을 사용할 수 있는 것이다. 은기..

[문제] N명의 사람들이 어떤 프로그래밍 대회에 참가했다. 대회에는 M개의 문제가 나왔다. 동철이는 이 프로그래밍 대회가 열렸다는 소식을 접했고, 간단한 웹 서핑으로 각 사람들이 문제를 풀었는지 아닌지를 나타내는 NⅹM 개의 값 ai,j를 구할 수 있었다. 사람에 1에서 N까지의 번호를 붙이고, 문제에도 1에서 M까지의 번호를 붙일 때, ai,j 는 대회가 끝나고 i번 사람이 j번 문제를 풀었다면 1, 풀지 못했다면 0을 가지는 값이다. 동철이는 이 대회에는 나가지 못했지만, 다른 프로그래밍 대회에 나갈 계획이고 목표는 우승이다. 그러므로 지금 열린 이 대회에서 1등을 한 사람들을 찾아 라이벌로 삼기로 했다. 이 대회에서 모든 문제의 점수는 같고 프로그램을 제출한 시간은 따지지 않는다. 그러므로, 푼 문..

[문제] 대박을 꿈꾸는 주혁이는 오늘 복권을 M장 구매했다. 각 복권에는 8자리의 고유 번호가 붙어 있다. 이 복권에는 여러 당첨 번호가 있어서 역시 8자리로 ‘*’혹은 숫자로 이루어져 있다. 복권의 고유 번호와 당첨 번호가 매치되면 당첨 번호에 따라 당첨금이 지급된다. ‘*’는 모는 숫자와 매치될 수 있다. 예를 들어 소지한 복권의 번호가 “20170101”인 경우, “***7****”이나 “2017****”같은 당첨 번호와는 매치가 되지만, “2016****”같은 당첨번호에는 매치되지 않는다. 이 복권의 모든 당첨 번호는 여러 복권이 당첨되지 않도록 설정되어 있다. 예를 들어 당첨 번호가 “***7****”, “2017****”인 경우는 없는 것이다. 왜냐하면 “20170101”가 둘 모두에 매치되기..

[문제] 직사각형과 점들이 있다. 각 점들이 다음 중 어떤 상태에 있는지 판별하여, 각각의 상태인 점이 몇 개씩 있는지 구하는 프로그램을 작성하라. 1. 점이 완전히 직사각형 내부에 있다. 2. 점이 직사각형의 네 변 중 적어도 하나의 위에 있다. 3. 점이 완전히 직사각형 외부에 있다. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 네 정수 X1, Y1, X2, Y2 ( -104 ≤ X1 ＜ X2 ≤ 104, -104 ≤ Y1 ＜ Y2 ≤ 104 )가 공백 하나로 구분되어 주어진다. 이는 직사각형이 xy평면 위의 네 점 ( X1, Y1 ), ( X1, Y2 ), ( X2, Y2 ), ( X2, Y1 )으로 이루어진 직사각형이라는 뜻이다. 두 번째 줄에는 ..

[문제] 규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다. 한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다. 한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다. 높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻고, 낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다. 이렇게 아홉 라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 이 게임의 승자가 된다. 두 사람의 총점이 같으면 무승부이다. 이번 게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다. 규영이가 내는 카드의 순서를 고정하면, 인영이가 어떻게 카드를 내는지에 따른 9..