문제 설명

1. A * (I - 1 < x= < I) 의 최소를 구하면 됨

풀이

x / A = 올림(I) 이다.
올림(I) * A = x -> (I - 1) * A = X

코드

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB27592320211385.305%

문제

창영이는 노래 여러 개를 이어서 부르는 가수이다. 유명한 노래의 비슷한 멜로디를 이어서 부르면서 언제 곡이 넘어갔는지 모르게 만드는 것이 창영이 노래의 특징이다. 이런 노래로 상업적으로 엄청난 성공을 거둔 창영이에게 큰 시련이 찾아왔다. 그것은 바로 저작권이었다.

창영이의 노래에 포함되어 있는 멜로디는 모두 저작권이 다른 사람에게 있는 노래이다. 따라서, 이 음악으로 상업적인 활동을 했기 때문에, 저작권 협회에 저작권료를 내야한다.

창영이는 자신의 앨범에 포함되어있는 저작권이 있는 멜로디의 평균값을 구해보기로 했다. 이 값은 아래와 같이 구할 수 있다.

(창영이 앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수) / (앨범에 수록된 곡의 개수)

이 때, 평균값은 항상 올림을 해서 정수로 만들어야 한다. 예를 들어, 창영이의 1집 앨범 "영창에서 영원히 영창피아노를 친다"에 총 38개 곡이 수록되어 있고, 이 앨범에 저작권이 있는 멜로디가 894개가 있다면, 평균값은 23.53이 되고 올림해서 24가 된다.

매니저 강산이는 얼마나 많은 사람에게 저작권료를 주어야 하는지 궁금해졌다. 강산이가 알고 있는 정보는 앨범에 수록되어 있는 곡의 개수와 위에서 구한 평균값이다. 이 때, 적어도 몇 곡이 저작권이 있는 멜로디인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 앨범에 수록된 곡의 개수 A와 평균값 I가 주어진다. (1 ≤ A, I ≤ 100)

출력

첫째 줄에 적어도 몇 곡이 저작권이 있는 멜로디인지 출력한다.

예제 입력 1 

38 24

예제 출력 1 

875


문제 설명

3 개의 숫자를 이용해서 연도를 나타낸다.
E, S, M 을 이용해서 해당 연도를 우리가 알고있는 연도로 변경하자

풀이

1. 0, 0, 0  에서 1 씩 증가시키면서 값을 확인한다.
2. 15, 28, 19 보다 높아지면 1 로 만들어주고 다시 (1) 을 실행한다.

코드


문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 숫자를 E, 태양을 나타내는 숫자를 S, 달을 나타내는 숫자를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 지나면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1 

1 16 16

예제 출력 1 

16

예제 입력 2 

1 1 1

예제 출력 2 

1

예제 입력 3 

1 2 3

예제 출력 3 

5266

예제 입력 4 

15 28 19

예제 출력 4 

7980


문제 설명

5 -> 6
6 -> 6
으로 변경했을 때, 최대값 + 최대값
5 -> 5
6 -> 5
으로 변경했을 때, 최소값 + 최소값
출력

풀이

1. String 의 replaceAll 사용해서 5 -> 6 6 -> 5 변경

코드


문제

상근이는 2863번에서 표를 너무 열심히 돌린 나머지 5와 6을 헷갈리기 시작했다.

싱근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5로 잘못 볼 수도 있다.

두 수 A와 B가 주어졌을 때, 상근이는 이 두 수를 더하려고 한다. 이 때, 상근이가 구할 수 있는 두 수의 가능한 합 중, 최소값과 최대값을 구해 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 A와 B가 주어진다. (1 <= A,B <= 1,000,000)

출력

첫째 줄에 상근이가 구할 수 있는 두 수의 합 중 최소값과 최대값을 출력한다.

예제 입력 1 

1430 4862

예제 출력 1 

6282 6292


문제 설명

연산자의 이해와 실수 연산을 이해하는지 확인하는 문제이다.

풀이

소수점 3 의 자리부터는 내림 처리를 하고 출력하면 된다.

해답

100 을 곱해주고 다 내림 처리 한다음 100 으로 나눈 후 출력한다.

문제

겨울 방학에 달에 다녀온 상근이는 여름 방학 때는 화성에 갔다 올 예정이다. (3996번) 화성에서는 지구와는 조금 다른 연산자 @, %, #을 사용한다. @는 3을 곱하고, %는 5를 더하며, #는 7을 빼는 연산자이다. 따라서, 화성에서는 수학 식의 가장 앞에 수가 하나 있고, 그 다음에는 연산자가 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄에는 화성 수학식이 한 줄에 하나씩 주어진다. 수학식은 100자를 넘지 않는다.

출력

각 테스트 케이스에 대해서, 화성 수학식의 결과를 계산한 다음에, 소수점 둘째 자리까지 출력한다.

예제 입력 1 

3
3 @ %
10.4 # % @
8 #

예제 출력 1 

14.00
25.20
1.00


문제 설명

중복된 수를 구하면 된다.

풀이

1. Bitset 을 사용하는 방법
bitset 은 bit 의 0 1 로 그 숫자가 있나 없나 확인하는 테크닉이다.
나중에 직접 구현해보면서 자세하게 적겠다.
2. 등차수열의 합을 이용하는 방법
S = N(N - 1)/2 + M
M = S - N(N - 1)/2


ISKU 님의 Buffer read 부분을 참고했습니다.

해답


문제

1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라.

입력

첫째줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.

둘째줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1부터 N – 1 사이의 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다.

출력

M을 출력하라.

예제 입력 1 

10
1 2 2 5 6 4 3 7 8 9

예제 출력 1 

2


문제 설명

1. 전쟁에서 누가 승리하는지를 알아내면 된다.
2. 전쟁에서 승리하는 기준은 점수가 높으면 된다.
3. 점수의 합은 정수이고, 32비트가 넘지 않는다. -> int 형으로 충분하다.

풀이 과정

코드를 작성하기 전에 이 문제는 너무 쉽다는 걸 알게돼, 만약 어떻게 이 문제의 코드를 짧게 짤 수 있을까와 동시에 유지보수를 쉽게 할 수 있을까? 라는 생각을 했다.
그리고 I/O 속도도 빠르면 좋다고 생각했다
1. BufferedReader 와 BufferedWriter 를 사용하자
2. StringTokenizer 로 문자열을 분해하자
3. 유지보수를 쉽게하기 위해 점수를 전역변수로 관리하자
4. 코드 라인이 짧아지는게 가능하겠다.

해답

1. 각 종족의 점수 * 종족의 수 = 점수
2. 점수 비교 점수
3. 출력

문제

중간계에 전쟁이 일어나려고 한다. 간달프는 사우론에 대항하기 위한 군대를 소집했고, 여러 종족이 이 군대에 가담했다. 전쟁을 시작하기 전에 간달프는 각 종족에 점수를 매겼다.

간달프의 군대의 각 종족의 점수는 다음과 같다.

  • 호빗 - 1
  • 인간 - 2
  • 엘프 - 3
  • 드워프 - 3
  • 독수리 - 4
  • 마법사 - 10

사우론의 군대의 점수는 다음과 같다.

  • 오크 - 1
  • 인간 - 2
  • 워그(늑대) - 2
  • 고블린 - 2
  • 우럭하이 - 3
  • 트롤 - 5
  • 마법사 - 10

중간계는 매우 신비한 곳이어서 각 전투의 승리는 날씨, 장소, 용맹에 영향을 받지 않는다. 전투에 참여한 각 종족의 점수를 합한 뒤, 큰 쪽이 이긴다.

전투에 참여한 종족의 수가 주어졌을 때, 어느 쪽이 이기는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, 독수리, 마법사 순서이다. 둘째 줄에는 사우론 군대에 참여한 종족의 수가 주어진다. 이 값 역시 공백으로 구분되어 있으며, 오크, 인간, 워그, 고블린, 우럭하이, 트롤, 마법사 순서이다. 모든 값은 음이 아닌 정수이고, 각 군대의 점수의 합은 32비트 정수 제한을 넘지 않는다.

출력

각 전투에 대해서, "Battle"과 전투 번호를 출력한다. 그 다음에 간달프의 군대가 이긴다면 "Good triumphs over Evil"를, 사우론의 군대가 이긴다면 "Evil eradicates all trace of Good", 점수의 합이 같아 이기는 쪽이 없다면 "No victor on this battle field"를 출력한다.

예제 입력 1 

3
1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 0 0 10
0 1 1 1 1 0 0
1 0 0 0 0 0
1 0 0 0 0 0 0

예제 출력 1 

Battle 1: Evil eradicates all trace of Good
Battle 2: Good triumphs over Evil
Battle 3: No victor on this battle field


1. O(N^3) 인 문제

문제

평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이 때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.

그림-1

여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.

그림-2

N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분의 면적을 구하는 프로그램을 작성하시오. 

입력

입력의 첫 번째 줄에는 색종이의 장수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 이어서 N장의 색종이에 관한 입력이 각 색종이마다 한 줄씩 차례로 주어진다. 색종이가 놓이는 평면은 가로 최대 101칸, 세로 최대 101칸으로 구성된 격자 모양이다. 격자의 각 칸은 가로, 세로 길이가 1인 면적이 1인 정사각형이다. 

편의상 가로 6칸, 세로 6칸으로 이루어진 격자의 예를 들어 설명하면, 각 칸에 표시된 값 (a,b)는 해당 칸의 번호를 나타낸다. 가장 왼쪽 아래의 칸은 (0,0) 가장 오른 쪽 위의 칸은 (5,5)이다. 

색종이가 놓인 상태는 가장 왼쪽 아래 칸의 번호와 너비, 높이를 나타내는 네 정수로 표현한다. 예를 들어, 위 그림에서 회색으로 표시된 색종이는 (1,4)가 가장 왼쪽 아래에 있고 너비 3, 높이 2이므로 1 4 3 2로 표현한다. 색종이가 격자 경계 밖으로 나가는 경우는 없다. 

출력

입력에서 주어진 순서에 따라 N장의 색종이를 평면에 놓았을 때, 입력에서 주어진 순서대로 각 색종이가 보이는 부분의 면적을 한 줄에 하나씩 하나의 정수로 출력한다. 만약 색종이가 보이지 않는다면 정수 0을 출력한다. 

예제 입력 1 

2
0 0 10 10
2 2 6 6

예제 출력 1 

64
36


1. 예전에 풀었던 이분탐색들이랑 비슷한 문제

2. 문제가 친절해서 0ml 인 경우는 없다.

3. r - 1 을 해줘야 답이 정상적으로 출력된다. (l 이 r 을 같거나 넘어가면서 r - 1 이 최대값이 됨)

문제

프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다.  즉 한 번 주문에 막걸리 용량이 802ml 이기도 1002ml가 나오기도 한다.  은상은 막걸리 N 주전자를 주문하고, 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 한다.  그런데 은상과 친구들은 다른 주전자의 막걸리가 섞이는 것이 싫어서, 분배 후 주전자에 막걸리가 조금 남아 있다면 그냥 막걸리를 버리기로 한다.  (즉, 한 번 주문한 막걸리에 남은 것을 모아서 친구들에게 다시 주는 경우는 없다.  예를 들어 5명이 3 주전자를 주문하여 1002, 802, 705 ml의 막걸리가 각 주전자에 담겨져 나왔고, 이것을 401ml로 동등하게 나눴을 경우 각각 주전자에서 200ml, 0m, 304ml 만큼은 버린다.) 이럴 때 K명에게 최대한의 많은 양의 막걸리를 분배할 수 있는 용량 ml는 무엇인지 출력해주세요.

입력

첫째 줄에는 은상이가 주문한 막걸리 주전자의 개수 N, 그리고 은상이를 포함한 친구들 K명이 입력된다. N은 10000이하의 정수이고, K는 1,000,000이하의 정수이다. 막걸리의 용량은 231 -1 보다 작거나 같은 자연수이다. (단, 항상 N ≤ K 이다. 즉, 주전자의 개수가 사람 수보다 많을 수는 없다 ) .

출력

첫째 줄에 K명에게 나눠줄 수 있는 최대의 막걸리 용량 ml 를 출력한다.

예제 입력 1 

2 3
702
429

예제 출력 1 

351

예제 입력 2 

4 11
427
541
774
822

예제 출력 2 

205

힌트

2번째 예제에서 205ml로 나눌 경우 2,2,3,4 가 된다. 하지만 206ml라고 하면 각각 2, 2, 2, 3 으로 나눌 수 있기 때문에 나누는 용량을 조금 줄여야한다.


1. 숫자를 입력받고 정렬해서 출력하면 된다.

2. 우선순위 큐를 사용했는데, 통과했다.

3. 원래 생각하던 솔루션은 입력받고 mergesort (quicksort 는 stack 메모리 초과될걸로 예상)

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절대값이 109보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

예제 입력 1 

2 2
3 5
2 9

예제 출력 1 

2 3 5 9

예제 입력 2 

2 1
4 7
1

예제 출력 2 

1 4 7

예제 입력 3 

4 3
2 3 5 9
1 4 7

예제 출력 3 

1 2 3 4 5 7 9

출처


1. 이번에는 홍대 문제를 풀어봐야겠다.

2. 간단한 구현 문제인데 풀고 난 후 깔끔한 솔루션이 생각났다.

3. 배열에 스왑되는 idx 를 미리 적어놓고 스왑하는 코드는 따로 빼놓으면, 유지보수가 하기 쉬워진다.

문제

야바위를 잘하는 재열이는 축제기간동안 홍문관 앞에 부스를 열어 돈을 벌어보려 한다. 

재열이는 컵 네 개를 일렬로 탁자 위에 올려놓고, 가장 왼쪽 컵에 작은 공 하나, 가장 오른쪽 컵에 큰 공 하나를 넣어놓았다. 이제 재열이는 컵 2개의 위치를 바꿔가면서 여러번 섞을 것이고, 모두 섞은 뒤에 상대방에게 어떤 컵에 공이 들어있는지 말하라고 할 것이다. 컵이 4개가 있을 때, 위치를 바꿀 수 있는 가능한 방법은 아래와 같이 6가지가 있다.

떼돈을 벌기 위해 3개월을 연습한 재열이에게 내기를 이길 수 있는 사람은 거의 없다.  그러나, 마침 엄청난 동체시력의 보유자 영범이 홍문관 앞을 지나고 있었다.  영범은 내기를 제안하고, 아무것도 모르는 재열이는 말없이 컵을 섞기 시작한다.  재열이의 손놀림이 아무리 빠르더라도, 영범이의 동체시력을 속일 수는 없다. 영범이는 동체시력뿐만 아니라, 기억력도 뛰어나서 재열이가 컵을 섞은 순서를 다 기억할 수 있다.  이것을 모르는 재열이의 운명은 당신이 작성할 프로그램에 달려있다.

재열이가 컵을 섞은 방법이 순서대로 주어질 때, 어떤 컵에 작은 공이 있는지, 어떤 컵에 큰 공이 있는지 차례대로 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에 재열이가 컵을 섞는 순서가 주어진다. 이 순서는 위 그림에 있는 A, B, C, D, E, F 중 하나이다. 재열이는 컵을 최대 200번 섞는다.

출력

첫번째 줄에는 작은 공이 있는 위치를, 두번째 줄에는 큰 공이 있는 위치를 출력한다. 공의 위치는 가장 왼쪽부터 1, 2, 3, 4로 표시한다.  

예제 입력 1 

AB

예제 출력 1 

2
4


+ Recent posts