으하하 공부일기

[문제] 삼삼 트리플(Samsam-Triple)은 여러 사람이 할 수 있는 게임이다. 이 게임에는 카드를 이용하는데, 카드에는 1에서 9까지의 숫자가 카드에 적혀 있고 적힌 숫자의 색이 빨강(R), 초록(G), 파랑(B)중의 하나로 총 27종류의 카드를 사용한다. 각 종류의 카드는 모두 4장씩 존재하여 총 108장의 카드로 게임을 진행한다. 이 게임에 참가하는 사람들은 9장의 카드를 패로 가져간다. 그리고, 차례를 번갈아 가면서 카드 한 장을 버린 다음 한 장을 새롭게 뽑아오는 것을 반복한다. 이렇게 순서대로 차례를 진행하다가 세 장의 카드로 이루어진 세트를 3개 만든 사람이 승리한다. 각 세트는 동일한 색의 카드 세 장으로 이루어져야 하며, 세 숫자가 모두 같거나, 세 숫자가 모두 연속된 숫자여야 한다..

[문제] 참가자들은 가장 처음 블록 위에서 가장 마지막 블록의 위로 이동해야 한다. 이 프로그램을 보고 있던 준홍이는 심심해서 이 장애물 경주가 얼마나 어려울지 난이도를 매겨 보기로 했다. 참가자가 이동하는 도중에 다음 블록의 높이가 현재 블록의 높이보다 높다면 올라가야 할 것이고, 다음 블록의 높이가 낮다면 내려가야 할 것이다. 준홍이의 생각에 이 둘은 서로 다른 능력을 필요로 하므로, 주어진 장애물에서 올라갈 때의 높이 변화와 내려갈 때의 높이 변화 둘 각각에 대해 가장 높이 변화가 심한 부분을 난이도라 하기로 했다. 예를 들어 위와 같이 장애물이 서 있다고 하자. 밑에 적힌 수가 직사각형 블록의 높이이다. 이 때, 올라갈 때 가장 심한 높이 변화는 60이고 내려갈 때 가장 심한 높이 변화는 40이다..

[문제] 어느날 희성이는 멀리 있는 물체는 보기가 힘들다는 생각을 했다. 그렇기에 다음과 같은 방식으로 물체가 얼마나 떨어져 있는지에 따라 다음처럼 수치를 매기기로 했다. 1. 0.1km 미만 : 0으로 매긴다. 2. 0.1km 이상 1km 미만 : 1으로 매긴다. 3. 1km 이상 10km 미만 : 2로 매긴다. 4. 10km 이상 100km 미만 : 3으로 매긴다. 5. 100km 이상 1000km 미만 : 4로 매긴다. 6. 1000km 이상 : 5로 매긴다. 어떤 물체와의 거리가 주어질 때, 위의 방식으로 수치를 매기는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 d(1 ≤ d ≤ 107)이 주어진다. d는 어떤 ..

[문제] 다솔이가 다니는 회사는 이번 달부터 월급을 상자에 담아 주기로 했다. 이 상자에는 pi의 확률로 xi만원이 들어 있다. 다솔이가 받을 수 있는 월급의 평균은 얼마인지 구해보자. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(2 ≤ N ≤ 20)이 주어진다. 다음 N개의 줄의 i번째 줄에는 하나의 실수 pi(0 < pi ≤ 1)과 하나의 정수 xi(1 ≤ xi ≤100,000)가 공백으로 구분되어 주어진다. pi는 소수점 이하 여섯 자리까지의 수를 가질 수 있다. pi의 총합은 1이다. [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고 한 칸을 띄운 후, 한 줄에 다솔이가 얻을 수 ..

[문제] 삼성시에 있는 5,000개의 버스 정류장은 관리의 편의를 위해 1에서 5,000까지 번호가 붙어 있다. 그리고 버스 노선은 N개가 있는데, i번째 버스 노선은 번호가 Ai이상이고, Bi이하인 모든 정류장만을 다니는 버스 노선이다. P개의 버스 정류장에 대해 각 정류장에 몇 개의 버스 노선이 다니는지 구하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N ( 1 ≤ N ≤ 500 )이 주어진다. 다음 N개의 줄의 i번째 줄에는 두 정수 Ai, Bi ( 1 ≤ Ai ≤ Bi ≤ 5,000 )가 공백 하나로 구분되어 주어진다. 다음 줄에는 하나의 정수 P ( 1 ≤ P ≤ 500 )가 주어진다. 다음 P개의 줄의 j번..

[문제] 정곤이는 자신이 엄청난 수학자임을 증명하기 위해, 어떤 규칙 만족하는 수를 찾아보기로 했다. 그 규칙은 단조 증가하는 수인데, 각 숫자의 자릿수가 단순하게 증가하는 수를 말한다. 어떤 k자리 수 X = d1d2…dk 가 d1 ≤ d2 ≤ … ≤ dk 를 만족하면 단조 증가하는 수이다. 예를 들어 111566, 233359는 단조 증가하는 수이고, 12343, 999888은 단조 증가하는 수가 아니다. 양의 정수 N 개 A1, …, AN이 주어진다. 1 ≤ i < j ≤ N 인 두 i, j에 대해, Ai x Aj값이 단조 증가하는 수인 것들을 구하고 그 중의 최댓값을 출력하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의..

[문제] 정점이 N개, 간선이 M개 있는 그래프가 주어진다. 정점에는 1번에서 N번까지의 번호가 붙어 있다. 이 때, i번 정점과 j번 정점 사이에, j번 정점과 k번 정점 사이에, k번 정점과 i번 정점 사이에 모두 간선이 있는 ( i, j, k ) (단, i < j < k )를 삼각형이라고 하자. 삼각형의 개수를 구하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 두 정수 이 공백으로 구분되어 주어진다. 이는 x번 정점과 y번 정점 사이에 간선이 있다는 의미이다. 반대로 y번 정점과 x번 정점 사이에 간선이 있다는 의미도 된다. 같은 간선을 의미하는 입력이 여러 번 주어..

[문제] 궁금증이 많은 한 소녀는 존 폰 노이만(John von Neumann)에게 다음과 같은 문제를 질문했다. “두 기차 A, B가 서로를 향해 달리고 있다. 두 기차의 전면부는 250마일 떨어져 있고 기차 A는 시속 10마일, B는 시속 15마일로 달리고 있다. 파리가 기차 A의 전면부에서 기차 B로 시속 20마일의 속력으로 날아간다. 파리가 기차 B의 전면부에 닿으면 바로 방향을 바꿔 기차 A를 향해 같은 속력으로 날아간다. 그러다 기차 A와 B가 충돌하면 파리는 죽을 것이다. 파리는 죽기 전 까지 몇 마일의 거리를 이동했을까?” 폰 노이만은 소녀의 질문에 대해 즉시 무한 급수를 이용해 답이 200마일이라는 것을 계산해냈다. 소녀가 질문한 문제의 조금 더 일반화된 버전을 해결해보자. [입력] 첫 ..