CodeDrive

문제:

상근이는 덧셈과 나눗셈을 엄청나게 못한다. 이런 상근이를 위해 정인이는 상근이에게 다음과 같은 문제를 냈다.

정인이는 양의 정수 A,B,C,D로 이루어진 2*2 표를 그렸다.

위와 같은 표가 있을 때, 표의 값은 A/C + B/D 이다.

상근이는 표를 몇 번 돌리면 표의 값이 최대가 되는지 궁금해졌다.

표는 90도 시계방향으로 돌릴 수 있다.

문제 상단의 표를 1 번 회전시키면 다음과 같다.

2번 회전 시키면 다음과 같이 된다.

표에 쓰여 있는 A,B,C,D가 주어졌을 때, 표를 몇 번 회전시켜야 표의 값이 최대가 되는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 공백으로 구분되어 주어진다. 둘째 줄에 C와 D가 공백으로 구분되어 주어진다. 모든 수는 100보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 표를 몇 번 돌려야 표의 값이 최대가 되는지 출력한다. 만약, 그러한 값이 여러개라면 가장 작은 값을 출력한다.

풀이방법:

사실 경우의 수가 4개 밖에 없기 때문에 0,90,180,270도 순으로 배열을 구성하도록 했다.

그리고 max 값의 index를 찾도록 했는데, 최대인 값이 여러개라고 하더라도 index는 가장 먼저 나오는 index를 반환하기 때문에 출력조건에 위배되지 않는다.

문제링크:

https://www.acmicpc.net/problem/2863

문제:

N*M 크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력:

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력:

첫째 줄에 정답 정사각형의 크기를 출력한다.

풀이방법:

N과 M의 크기가 50보다 작기 때문에 브루트 포스로 전부 탐색을 해도 된다. 1x1의 정사각형은 반드시 존재하기 때문에 넘어가고 가로, 세로 길이가 2인 정사각형부터 탐색을 시작한다. 한 변의 길이가 n이지만 좌표상의 차이는 n-1이 나게 된다. 따라서 이 점을 이용해서 꼭짓점의 값들이 같은지 탐색하고 같다면 answer를 변경하도록 한다.

만약 모두 탐색을 했는데 초기 answer이 변하지 않는다면 가장 큰 정사각형은 1x1이므로 1을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/1051

문제:

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=100,000,000)이 주어진다.

출력:

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이방법:

처음에는 브루트 포스로 알고리즘 분류가 되어 있어서 그냥 N까지의 수를 다 붙인 다음에 길이를 구하는 방식으로 했는데 시간초과가 발생했다.

그래서 처음 받은 N을 기준으로 자릿수를 줄여나가면서 더하는 방식으로 바꾸어서 해결을 했다.

ex) 3자리수의 갯수*3 + 2자리수의 갯수*2 ....

문제링크:

https://www.acmicpc.net/problem/1748

문제:

동호는 새악대로 T 통신사의 새 핸드폰 옴머나를 샀다. 새악대로 T 통신사는 동호에게 다음 두 가지 요금제 중 하나를 선택하라고 했다.

1. 영식 요금제

2. 민식 요금제

영식 요금제는 30초마다 10원씩 청구된다. 이 말은 만약 29초 또는 그 보다 적은 시간 통화를 했으면 10원이 청구된다. 만약 30초부터 59초 사이로 통화를 했으면 20원이 청구된다.

민식 요금제는 60초마다 15원씩 청구된다. 이 말은 만약 59초 또는 그 보다 적은 시간 통화를 했으면 15원이 청구된다. 만약 60초부터 119초 사이로 통화를 했으면 30원이 청구된다.

동호가 저번 달에 새악대로 T 통신사를 이용할 때 통화 시간 목록이 주어지면 어느 요금제를 사용 하는 것이 저렴한지 출력하는 프로그램을 작성하시오.

입력:

동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 싼 요금제의 이름을 출력한다. 그 후에 공백을 사이에 두고 요금이 몇 원 나오는지 출력한다. 만약 두 요금제의 요금이 모두 같으면 영식을 먼저 쓰고 민식을 그 다음에 쓴다.

영식은 Y로, 민식은 M으로 출력한다.

풀이방법:

처음에 정답 비율이 30%대이길래 난이도가 있는 문제인 줄 알았는데 생각보다 간단했던 문제였다.

통화한 시간들을 배열에 담고 각 30초, 60초로 나눈 몫에 1을 더하고 10원, 15원을 곱한 것들을 계속 누적해서 더하고 나 중에 이를 비교해 형식에 맞게 출력하면 되는 문제였다.

아마도 정답률이 낮았던 이유가 형식을 맞지 못하게 출력해서 그런 것 같으므로 python의 format을 사용해서 형식을 맞춰 주었다.

문제링크:

https://www.acmicpc.net/problem/1267

문제:

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 시험장의 개수 N(1<=N<=1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai(1<=Ai<=1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다.(1<=B,C<=1,000,000)

출력:

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

풀이방법:

총감독관은 시험장마다 1명씩만 존재해야 하므로 answer를 시험장의 수로 초기화한다. 

그리고 각 시험장마다 총감독관이 감시할 수 있는 인원을 빼고 아직 감시해야 할 인원들이 남았다면 이를 부감독관에게 할당하도록 한다. 

문제링크:

https://www.acmicpc.net/problem/13458

문제:

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3+5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 +17 = 7+13, 42 = 5+37 = 11+ 31 = 13 + 29 = 19 +23 이다.

이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력:

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 <= n <=1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스에 대해서, n = a+b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자를 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong"을 출력한다.

풀이방법:

 여러 케이스에서 소수를 사용해야 하는데, 그 때마다 계산을 해야 하는 소수들을 구하면 너무 오랜 시간이 걸리기 때문에 최대 1,000,000를 넘지 않는다는 것을 이용해서 미리 소수들을 구하도록 한다. 

 따라서 소수를 효율적으로 구할 수 있는 방법 중 하나인 에라토스테네스의 체 방법을 사용해서 배열을 구한다. 그 뒤로는 입력으로 들어온 n 이하에 존재하는 소수들에 대해서 합을 구해본다. 이 때 n//2까지만 반복문을 돌아도 되는데, 그 뒤에 있는 값들은 이미 이 전에 검사했을 것이기 때문이다. (ex) 3+5=8, 5+3=8)

 그리고 두 수간의 차이가 가장 큰 경우를 출력해야 하므로 작은 수부터 즉 3부터 확인을 하며 처음으로 추측을 만족시킬 때가 간격이 가장 크기 때문에 break를 걸고 형식에 맞게 출력을 하도록 한다.

 원래는 추측이 틀렸을 때에는 지정된 문구를 출력해야 하지만, 이 추측은 실제로 존재하며 아직 반례를 찾지 못했기 때문에 틀린 경우가 없기 때문에 생략했다.

문제링크:

https://www.acmicpc.net/problem/6588

문제:

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력:

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다. (3<=N<=100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력:

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

풀이방법:

N개의 최대공약수를 구하는 문제라고 생각하였다. 처음에 가로수가 심어져 있는 위치를 받았을 때, 각 가로수 사이의 간격을 측정해서 배열에 담도록 하였다. 이들을 최대한 균일하게 자르기 위해서는 이 수들의 최대공약수를 구해야 한다고 생각했다. 따라서 temp라는 배열에 복사를 하고 while문을 통해서 N개 수 최대공약수 문제를 풀었다.

마지막으로는 이렇게 구한 최대공약수를 통해 각 간격마다 나누어 주어서 심어야 할 가로수의 개수를 구했다.

문제링크:

https://www.acmicpc.net/problem/2485

문제:

독일 로또는 {1, 2, ... , 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k개의 수를 골라 집합 S를 만든 다음 그 수만을 가지고 번호를 선택하는 것이다.

예를 들어 , k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1,2,3,5,8,13].[1,2,3,5,8,21].[1,2,3,5,8,34],[1,2,3,5,13,21], ... ,[3,5,8,13,21,34]}

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k(6<k<13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

풀이방법:

 경우의 수를 구하는 문제는 python의 itertools를 사용하면 쉽게 구할 수 있다. itertools.combinations( iterable, k )와 같은 방식으로 사용하면 iterable한 자료형에서 k를 골라 만들 수 있는 모든 경우의 수를 만들어 준다.

 이 경우의 수를 출력하기 위해 *c와 같이 사용을 하고 각 테스트 케이스 사이에는 빈 줄을 하나 출력해야 하므로 print()를 마지막에 넣어주었다.

문제링크:

https://www.acmicpc.net/problem/6603

문제:

김탑은 TV를 사러 인터넷 쇼핑몰에 들어갔다. 쇼핑을 하던 중에, TV의 크기는 그 TV의 대각선 길이로 나타낸다는 것을 알았다. 하지만, 김탑은 대각선의 길이가 같다고 해도, 실제 TV의 크기는 다를 수도 있다는 사실에 직접 TV를 보러갈걸 왜 인터넷 쇼핑을 대각선의 길이만 보고있는지 후회하고 있었다.

인터넷 쇼핑몰 관리자에게 이메일을 보내서 실제 높이와 실제 너비를 보내달라고 했지만, 관리자는 실제 높이와 실제 너비를 보내지 않고 그것의 비용을 보내왔다.

TV의 대각선 길이와, 높이 너비의 비율이 주어졌을 때, 실제 높이와 너비의 길이를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 TV의 대각선 길이, TV의 높이 비율, TV의 너비 비율이 공백 한 칸을 사이에 두고 주어진다. 대각선 길이는 5보다 크거나 같고, 1,000보다 작거나 같은 자연수, 높이 비율은 1보다 크거나 같고, 99보다 작거나 같은 자연수 너비 비율은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. 너비 비율은 항상 높이 비율보다 크다.

출력:

첫째 줄에 TV의 높이와 TV의 너비를 공백 한 칸을 이용해서 구분지은 후 출력한다. 만약 실제 TV의 높이나 너비가 소수점이 나올 경우에는 그 수보다 작으면서 가장 큰 정수로 출력한다. (예)1.7->1

풀이방법:

높이와 너비의 비율이 주어졌으므로 이들의 비율 1에 해당하는 r을 구하면 된다. 이 r은 대각선의 길이로 구할 수 있게 된다. 너비를 x, 높이를 y라고 했을 때, x²+y²=기울기² 를 만족하고, x:y=a:b 의 비율을 만족시키는 r이 있다고 하자.

(r은 x=a*r, y=b*r 을 만족한다.)

그러면 다음을 만족한다.

a²r²+b²r²=기울기²

따라서 r로 묶어서 계산할 수 있고, 최종적으론 a*r, b*r을 출력하면 된다.

문제링크:

https://www.acmicpc.net/problem/1297

문제:

정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고..(이하 생략) 이러한 연산을 한 결과를 출력하시오.

입력:

첫째 줄에 정수 N이 주어진다. (0<=N<=99,999,999)

출력:

첫째 줄에 위와 같은 연산을 한 결과를 출력하시오.

풀이방법:

뒷자리에서 부터 하나씩 반올림을 하면서 진행하면 된다. 반올림을 하려고 하는 자릿수가 5이면 앞자리에 1을 더해주고, 그렇지 않다면 그 자리를 0으로 바꾼 뒤 그대로 이어붙이면 된다. 그런데 반올림을 하는 자리의 수가 5이상이고 1을 받는 자리가 9이면 문제가 발생한다. 이 경우에는 9가 1을 받아서 10이 되기 때문에 그 앞자리까지에도 영향을 받게 된다. 

이를 int 연산으로 바꾸어서 진행을 했다면 문제가 없겠지만 str의 슬라이싱을 사용해서 문제를 풀고 있기 때문에 이 경우를 따로 예외 케이스로 만들어서 해결해 주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2033