CodeDrive

문제:

풀이방법:

 원점과 거리가 모두 d인 위치라는 것은 원을 의미한다. 조건상으로는 1사분면에 있는 사분원 내의 정수 점을 찾으면 되는 문제다. x와 y를 모두 변경하면서 조건을 만족하는 점을 찾는 방법을 사용할 수 있지만, 시간초과가 발생하게 된다. 따라서 x를 먼저 결정하고 피타고라스 정리를 사용하여 최대 길이의 y를 찾아 가능한 경우의 수를 모두 찾도록 한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/140107

문제:

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

출력:

각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.

풀이방법:

 오른쪽 끝에 0이 생기기 위해서는 2x5가 곱해져야 한다. 즉, N!을 소인수 분해 했을 때, 2와 5 중 더 작은 인수가 0의 갯수가 될 것이다. (2^P, 5^Q 일 때 P, Q 중 더 작은 수) 하지만 10까지만 봤을 때에도 2의 갯수가 압도적으로 많기 때문에 5의 개수만 알면 바로 0의 갯수를 알 수 있다. 따라서 5의 인수를 구하도록 한다.

문제링크:

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

문제:

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력:

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

풀이방법:

 2차원 평면에서 점 3개의 방향을 판단하는 알고리즘을 CCW(Counter Clockwise)라고 한다. 외적을 사용하는 알고리즘인데, 아래 링크에서 자세하게 잘 설명해준 것 같아서 참조하도록 한다.

참고링크: https://degurii.tistory.com/47

문제링크:

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

문제:

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

입력:

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

출력:

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

풀이방법:

 어떤 두 자연수를 A, B라고 하고, 최대공약수를 G,  최소공배수를 L이라고 하자. 최대공약수는 공통인 약수들 중에서 가장 큰 수이기 때문에 두 자연수 A, B는 A=aG, B=bG와 같이 표현할 수 있다. 그리고 최소공배수는 두 자연수의 공통인 배수들 중에서 가장 작은 수이므로 L=abG라고 표현할 수 있다. (aG와 bG의 공통의 배수이기 때문)

 따라서 최대공약수와 최소공배수 간의 관계는 ab= L/G라고 할 수 있다. A와 B를 찾기 위해 G는 이미 알고 있으므로 가능한 a와 b를 구하도록 한다. 즉, ab의 약수들을 찾으면 되는 문제다.

 ab의 약수들을 기반으로 A와 B 값을 구한 뒤에 문제의 조건처럼 두 자연수의 합이 최소가 되도록 정렬을 수행하여 두 수를 찾는다. 

문제링크:

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

문제:

N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경우 (7, 4, 9)를 선택하면 합이 20이 되어 일의 자리 수는 0이 되고, (5, 5, 9)를 선택하면 합이 19가 되어 일의 자리 수는 9가 된다. 게임을 이기기 위해서는 세 장의 카드를 선택할 때 그 합의 일의 자리 수가 가장 크게 되도록 선택하여야 한다.

예를 들어, N=3일 때

• 1번 사람이 (7, 5, 5, 4, 9),
• 2번 사람이 (1, 1, 1, 1, 1),
• 3번 사람이 (2, 3, 3, 2, 10)의 

카드들을 받았을 경우, 세 수의 합에서 일의 자리 수가 가장 크게 되도록 세 수를 선택하면

• 1번 사람은 (5, 5, 9)에서 9,
• 2번 사람은 (1, 1, 1)에서 3,
• 3번 사람은 (2, 3, 3)에서 8의

결과를 각각 얻을 수 있으므로 첫 번째 사람이 이 게임을 이기게 된다.

N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

입력:

첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다.

출력:

게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

풀이방법:

 시간복잡도가 N이며, N은 최대 1000이기 때문에 브루트 포스 방법으로 해결해도 된다. 각 사람들에 대해서 모든 조합을 구한 뒤 가장 큰 일의 자리의 수를 가지고 있는 사람을 찾으면 된다.

문제링크:

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

문제:

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력:

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력:

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

풀이방법:

 주어질 수 있는 첫 번째 수가 크지 않기 때문에 브루트 포스 방법으로 모든 케이스를 고려하여 해결하면 된다. 1부터 N까지 반복하여 두 번째 수를 결정하고 3번, 4번의 과정을 진행한다. 4번으로 인해 더 이상 수를 만들지 않을 때마다 생성한 수들의 갯수를 비교하여 이전 케이스보다 큰 경우에만 기록하도록 한다.

문제링크:

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

문제:

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력:

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

풀이방법:

 처음에 모든 물병에 물이 1리터씩 들어있고, 이를 한 물병에 합치는 과정을 하는 과정은 이진수를 더하는 것과 같다. 예를 들어, N=3, K=1일 때를 보면, 물병이 3개가 있다는 것은 이진수로 보면 11(3)과 같고, 실제로 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남아있다. 만약 상점에서 한 개의 물병을 산다면, 4리터가 들어있는 물병 한 개를 만들 수 있다. (11+1 =100) 

 즉, 이 문제는 주어진 N을 2진수로 변경한 뒤에 1씩 더하면서, 더한 값의 이진수 값에 1의 값이 K개 있을 때까지 반복하여 더해주면 된다.

문제링크:

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

문제:

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.

빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.

위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다.

출력:

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

풀이방법:

 시작점, 도착점과 입력으로 들어온 원의 중심과 거리를 비교하여 원 안에 있는지 밖에 있는지 확인한다. 원의 반지름과 각 거리를 비교했을 때, 각 경우의 수는 다음을 의미한다.

• 각 거리들이 반지름 r보다 클 때, 원의 밖에 있는 것을 의미하고, 반지름 r 보다 작다면, 원의 안에 있는 것을 의미한다.
  • 따라서 둘 다 밖에 있거나 안에 있다면 행성계 진입/이탈이 필요하지 않다.
  • 둘 중 한 거리만 안에 있다면 이 때는 행성계 진입/이탈이 필요하므로 이 경우의 수에 대해서만 count 한다.

문제링크:

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

문제:

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력:

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

풀이방법:

해당 문제는 다음과 같은 알고리즘으로 해결하도록 한다.

1. n개의 a m개의 z가 있다고 했을 때, a를 하나 제거했을 때의 경우의 수를 구한다.

2. 이 갯수가 k보다 크다면 a를 먼저 배치한다.

2-1. 이 갯수가 k보다 작다면 z를 먼저 배치하고, k에서 1에서 구한 값을 빼준다.

3. n이나 m 둘 중 하나가 0이 될 때까지를 이를 반복하고, 남은 n과 m이 있다면 다 이어붙이고 종료한다.

문제링크:

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

문제:

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라

입력:

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력:

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

풀이방법:

 수학 시간에 배웠던 경로의 갯수 공식을 사용하도록 한다. 사각형이 있고, 되돌아 갈 수 없다는 조건이 있다면 시작점에서 도착점까지 가는 경우의 수는 (가로변의 갯수 + 세로변의 갯수)C(가로변의 갯수 or 세로변의 갯수)다. 이 문제의 경우 격자에 하나의 중심점이 표현되어 있기 때문에, 이 점을 기준으로 두 번의 경우의 수를 구한 다음에 둘을 곱하면 최종 답을 얻을 수 있다.

 따라서 이 문제는 O 표시가 되어 있는 지점의 좌표를 정확하게 계산하고, combination 연산 공식을 구현하여 문제를 해결하면 된다.

문제링크:

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