CodeDrive

문제:

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력:

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

풀이방법:

https://ko.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98

GCD(n,k) = 1 는 n과 k가 서로수임을 의미하는 것이고, n과 서로소인 정수의 갯수를 세는 방법은 정수론에서 오일러 피 함수가 있다. 

오일러 피 함수를 간략히 설명하면 다음과 같다. 오일러 피 함수는 주어진 n의 소인수를 구한 뒤에, 각 소인수들의 (1-1/p)를 구해 n에 곱해주면 서로소의 갯수를 구할 수 있다. 따라서 이 함수를 python으로 구현하여 다음과 같이 계산하도록 한다.

문제링크:

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

문제:

지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

입력:

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

풀이방법:

 0부터 9까지는 각 숫자가 한번씩 나온다는 사실을 사용해서 이 문제를 해결한다.

예를 들어 N이 99로 주어진다면 일의 자리만 보았을 때, 0~9가 총 10번 나타나고, N이 29로 주어진다면 0~9는 총 3번 등장할 것이다. 즉, 십의 자리에 따라서 나오는 횟수가 달라지게 된다.

 일의 자리가 아닌 다른 자릿수도 그와 유사하게 구할 수 있다. 다만 각 자릿수에 따른 배수를 고려해야 한다. 19의 경우 십의 자리만 봤을 때, 10~19까지 1이 총 10번 등장하는 것을 알 수 있다. 즉 각 자릿수에 따라 1배, 10배, 100배, ... 만큼의 갯수가 존재한다고 생각하면 된다.

 0~9의 틀을 고정하기 위해서 매 N의 일의 자리를 9로 고정시켜주도록 한다. N이 121일 때의 예시로 코드가 돌아가는 것을 확인해본다.

우선 121의 일의 자릿수를 9로 만들기 위해 121, 120만 따로 계산해주도록 한다. 이 과정이 끝나면 N=119가 되고, answer는 [1, 3, 2, 0, 0, 0, 0, 0, 0, 0]가 된다.

119에서 일의 자리에서 0~9는 총 12번 나타나게 된다. 따라서 각 answer에 12를 더해주고, 책 페이지의 시작은 1이기 때문에 0의 자릿수만 하나 빼주도록 한다. 이 과정이 끝나면 N=11이 되고, answer는 [12, 15, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.

N = 11이기 때문에 9로 만들어주도록 한다. 11과 10만 따로 계산을 진행하며, 이 때 배수는 10이기 때문에 N=9, answer는 [22, 45, 14, 12, 12, 12, 12, 12, 12, 12]가 된다.

 십의 자리에서 0~9가 총 1*10번 나타나게 된다. 따라서 각 answer에 10을 더해주고, 십의 자리에서 0은 존재할 수 없기 때문에 0의 자릿수만 빼주도록 한다. (01, 02, 03, ... 은 존재하지 않음)

따라서 최종적으로 22 55 24 22 22 22 22 22 22 22 의 값을 가지게 된다.

문제링크:

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

문제:

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력:

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

풀이방법:

 한 문제에 K번째 수열을 구하는 문제와 주어진 수열이 몇 번째인지 구하는 문제가 합쳐져 있다. 두 소문제는 주어진 수 중 맨 앞의 숫자로 구별되며, 이를 command(c)로 구분해 각 소문제를 풀도록 한다.

 첫 번째 소문제는 K번째 수열을 구하는 문제다. 앞의 자릿수부터 계산하며, 주어진 수 K로부터 만들 수 있는 경우의 수를 빼주며 한자리씩 정해나간다. 즉, 예제의 경우 3번째 수열을 구하는 문제에서 맨 앞자리를 a인 경우의 수는 3!개이다. 따라서 3번째 수열은 0~3!번째 수열에 속할 것이므로, 맨 앞자리는 1인 것을 알 수 있다. 이러한 방법을 계속하여 k번째 수열을 찾는다.

 두 번째 소문제는 첫 번째 소문제의 역으로 구할 수 있다. 팩토리얼을 사용해 k번째 수열을 구했던 것의 역으로 팩토리얼을 더하면서 k를 찾도록 한다.

문제링크:

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

문제:

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력:

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

풀이방법:

 주어진 조건에 따라 수행하게 하는 구현문제다. 앞에서부터 순차적으로 두 사람을 뽑은 뒤에 각 사람이 k와 l인지 확인하고, 둘 중 하나에 해당하면 그 사람이 무조건 이기게 한다. 만약 각각 k와 l에 해당하면 반복문을 중단시킨다.(만약 둘다 아니라면 먼저 들어온 사람을 이기게 한다.) 

문제링크:

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

문제:

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력:

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력:

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

풀이방법:

 소수를 찾기 위한 에라토스테네스의 체와 그리고 한 소수로부터 다른 소수로 이동하기 위한 bfs를 사용하는 문제다.

우선 네 자리 수인 모든 소수를 찾기 위해서 에라토스테네스의 체를 사용한다. 에라토스테네스의 체를 1부터 10000까지 적용을 한 뒤에 filter를 사용해 1000보다 큰 수들만 남기도록 한다.

 네 자리 소수를 모두 구한 뒤에는 bfs를 사용해서 기준이 되는 숫자와 네 자리 소수를 모두 비교해서 하나만 다른 경우에만 새 queue에 넣는 방식으로 진행한다. 이 때 중복 방문을 피하기 위해서 visited 배열을 사용한다. 만약 목적지 소수를 발견하면 bfs를 종료하고 answer를 출력하며, 만약 모든 소수를 방문해도 도달하지 못했다면 Impossible을 출력하게 한다.

문제링크:

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

문제:

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력:

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

풀이방법:

1. 산술평균 : sum 함수를 통해서 합계를 구하고 N으로 나눈 뒤 round 한다.

2. 중앙값 : 배열을 정렬하고, N//2의 인덱스 값을 출력한다. (항상 홀수 길이를 가지고 있기 때문에 가능)

3. 최빈값 : collections의 Counter를 사용해서 각 값의 출력 횟수를 구하고, most_common으로 빈도수로 정렬한다. 이 때, 최빈값이 여러 개 있는지 확인한 후 적절하게 출력하도록 한다.

4. 범위 : 배열의 최댓값에서 최솟값을 뺀다.

문제링크:

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

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

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

문제:

N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.

풀이방법:

 처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.

 하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.

따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다. 

우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.

N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)

이를 정리하면 다음과 같이 표현할 수 있다.

N = LX + (1+2+3+...+L-1)

   = LX + (L-1)L/2

그럼 X는 다음과 같이 구할 수 있다.

X = N/L - (L-1)/2

따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.

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

문제:

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력:

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력:

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

풀이방법:

 N개의 숫자들을 M으로 나눴을 때 나머지가 모두 같은 M을 찾기 위해서는 N개의 숫자들을 큰 순서로 정렬한 뒤에 그들의 차를 구하고 GCD를 계산하면 된다. 이 것이 가능한 이유는 간략히 설명하면 다음과 같다. 

 숫자 A, B가 있고 M으로 나누면 나머지가 R로 같다고 하자. 그러면 다음과 같이 식으로 쓸 수 있다.

A = a*M + R

B = b*M + R

이들의 차를 구하면 다음과 같이 된다.

A-B = (a-b)*M

따라서 M은 A와 B의 GCD를 의미하게 되고 가능한 M은 해당 GCD들의 약수일 것이다.

python의 math.gcd를 사용하고, 이 값에 대해 약수를 구하는 함수를 구해 M을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2981

문제:

근우는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4x9)장이다. 근우가 배운 카드 게임은 36장의 카드에서 5장을 뽑고, 아래와 같은 규칙으로 정수를 계산하는 것이다.

각 카드는 다음과 같이 나타낸다. 카드의 색깔은 영어 대문자 R, B, Y, G로 나타내는데, R은 빨간색, B는 파란색, Y는 노란색, G는 녹색을 뜻한다. 예를 들어서 Y8은 노란색 8을 나타내고, B5는 파란색 5를 나타낸다.

<점수를 정하는 규칙>

1. 카드 5장이 모두 같은 색이면서 숫자가 연속적일 때, 점수는 가장 높은 숫자에 900을 더한다. 예를 들어, 카드가 Y4, Y3, Y2, Y5, Y6 일 때 점수는 906(=6+900)점이다.
2. 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 예를 들어, 카드가 B3, R3, B7, Y3, G3 일 때 점수는 803(=3+800)점이다.
3. 카드 5장 중 3장의 숫자가 같고 나머지 2장도 숫자가 같을 때 점수는 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 예를 들어, 카드가 R5, Y5, G7, B5, Y7 일 때 점수는 757(=5x10+7+700)점이다.
4. 5장의 카드 색깔이 모두 같을 때 점수는 가장 높은 숫자에 600을 더한다. 예를 들어, 카드가 Y3, Y4, Y8, Y6, Y7 일 때 점수는 608(=8+600)점이다.
5. 카드 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 500을 더한다. 예를 들어 R7, R8, G9, Y6, B5 일 때 점수는 509(=9+500)점이다.
6. 카드 5장 중 3장의 숫자가 같을 때 점수는 같은 숫자에 400을 더한다. 예를 들어 R7, Y7, R2, G7, R5 일 때 점수는 407(=7+400)점이다.
7. 카드 5장 중 2장의 숫자가 같고 또 다른 2장의 숫자가 같을 때 점수는 같은 숫자 중 큰 숫자에 10을 곱하고 같은 숫자 중 작은 숫자를 더한 다음 300을 더한다. 예를 들어, R5, Y5, Y4, G9, B4 일 때 점수는 354(=5X10+4+300)점이다.
8. 카드 5장 중 2장의 숫자가 같을 때 점수는 같은 숫자에 200을 더한다. 예를 들어, R5, Y2, B5, B3, G4 일 때 점수는 205(=5+200)점이다.
9. 위의 어떤 경우에도 해당하지 않을 때 점수는 가장 큰 숫자에 100을 더한다. 예를 들어, R1, R2, B4, B8, Y5 일 때 점수는 108(=8+100)점이다.

입력으로 카드 5장이 주어질 때, 카드 게임의 점수를 구하는 프로그램을 작성하시오. 두 가지 이상의 규칙을 적용할 수 있는 경우에는 가장 높은 점수가 카드 게임의 점수이다.

입력:

첫째 줄부터 다섯째 줄까지 한 줄에 카드 하나씩 입력된다. 카드의 색깔과 숫자 사이에는 빈 칸이 하나 있다.

출력:

한 줄에 카드의 점수를 출력한다.

풀이방법:

 주어진 규칙에 알맞게 점수계산을 하면 된다. 규칙 조건에 따라 중복으로 계산이 되는 경우가 존재하는데 조건문을 통해 최댓값을 가지도록 한다.

규칙을 크게 보면 다음과 같이 세 가지가 있다.

<색 조건>

1. 모두 같은 색을 가지는 가?

<숫자 조건>

2. 숫자가 연속 되는가?

3. 공통된 숫자가 K개 있다.

따라서 각 조건에 대해 다음과 같은 방법을 사용한다.

1. set 연산을 사용해 원소의 갯수가 1이면 모두 같은 색이다.

2. 가장 큰 값과 가장 작은 값의 차이가 4면 연속되어 있다.

3. 숫자가 key, 갯수가 value은 dict 자료형을 사용한다.

위 방법들 사용해서 해당하는 규칙을 찾고 그에 맞게 계산하면 된다.

문제링크:

www.acmicpc.net/problem/2621