CodeDrive

문제:

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다.

출력:

가능한 모든 비밀번호의 개수를 출력한다.

풀이방법:

 처음에는 dfs를 활용한 백트래킹 방법으로 풀었다가 시간초과가 발생했다. 다른 방법을 생각해보던 중 수학적으로 풀 수 있음을 알게 되었다.

 따라서 포함배제의 원리를 사용해서 이 문제를 푼다. 문제에서 주어지는 n과 m만을 사용해서 풀수 있다.

m개의 수를 반드시 포함하는 경우의 수를 구하기 위해서 전체 가능한 경우의 수에서 m개의 수를 포함하지 않는 경우의 수를 빼는 것으로 구한다. 즉 다음과 같다.

비밀번호에 들어가는 수 m을 반드시 포함하는 비밀번호의 수 = 전체 비밀번호의 수 - m개의 수가 포함되지 않은 비밀번호의 수

전체 경우의 수는 10^n가 된다. m개의 수가 포함되지 않은 비밀번호의 수는 포함배제의 원리를 사용해서 구하도록 한다. 즉 구하는 식은 다음과 같이 된다.

answer = 10^n - mC1*9^n+mC2*8^n-mC3*7^n+.....

문제링크:

www.acmicpc.net/problem/13908

문제:

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 주사위를 쌓아서 N*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.

1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.

2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.

3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.

 주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.

 N이 1인 경우는 위에서 구한 케이스 구분이 필요없기 때문에 따로 처리하도록 한다.

문제링크:

www.acmicpc.net/problem/1041

문제:

Lucky Set이란 정수의 집합이다.

구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.

구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.

Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.

출력:

첫재 줄에 문제의 정답을 출력한다.

풀이방법:

N이 Lucky set의 어느 구간에 속해 있는지 파악해야 한다. 이 때, N이 lucky set의 원소일 수 있으므로 주의해서 탐색해야 한다. 반복문을 사용해서 N이 속해 있는 구간을 파악하고 왼쪽 값을 left, 오른쪽 값을 right라고 설정한다. N이 lucky set의 원소보다 다 작은 경우는 예외케이스로 판단하도록 한다.

left 와 right를 구한 뒤에는 이중반복문을 사용해서 구간을 생성하여, 이 구간 내에 N이 있는 경우에만 answer에 값을 더하도록 한다.

문제링크:

www.acmicpc.net/problem/1059

문제:

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다.

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단, 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3+6+3과 12=3+3+6은 다른 방법이다.

입력:

임의의 3의 배수 자연수 n이 주어진다. (3<=n<=3000)

출력:

자연수 n을 분해하는 방법의 개수를 출력하라.

풀이방법:

고등학교 수학이 생각나는 문제다. 이 문제를 변수로 나타내면 x+y+z = n (x,y,z,n은 3의 배수) 와 같고, 이는 조합 문제와 동일하다.

1. 간결하게 표현하기 위해 모든 수가 3의 배수이므로 3으로 나눠준다. (x'+y'+z' = n//3, x',y',z'>=0)

2. 3의 배수의 자연수로 분해를 해야 하기 때문에 좌변에 3을 빼줌으로써 해결한다. (x''+y''+z'' = n//3-3, x''+y''+z''>=1), 이는 nHr을 계산하는 문제와 같아진다.(3Hn//3-3)

따라서 이를 계산하면 답을 구할 수 있다.

문제링크:

www.acmicpc.net/problem/16561

문제:

수현이는 4차 산업혁명 시대에 살고 있는 중학생이다. 코로나 19로 인해, 수현이는 버추얼 학교로 버추얼 출석해 버추얼 강의를 듣고 있다. 수현이의 버추얼 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.

다음 연립 방정식에서 x와 y의 값을 계산하시오.

4차 산업혁명 시대에 숙제나 하고 앉아있는 것보다 버추얼 친구들을 만나러 가는 게 더 가치있는 일이라고 생각했던 수현이는 이런 연립방정식을 풀 시간이 없었다. 다행히도, 버추얼 강의의 숙제 제출은 인터넷 창의 빈 칸에 수들을 입력하는 식이다. 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다. 수현이가 버추얼 친구들을 만나러 버추얼 세계로 떠날 수 있게 도와주자.

입력:

정수 a,b,c,d,e,f가 공백으로 구분되어 차례대로 주어진다. (-999<=a,b,c,d,e,f<=999)

문제에서 언급한 방정식을 만족하는 (x,y)가 유일하게 존재하고, 이 때 x와 y사 각각 -999 이상 999 이하의 정수인 경우만 입력으로 주어짐이 보장된다.

출력:

문제의 답인 x와 y를 공백으로 구분해 출력한다.

풀이방법:

연립방정식을 푸는 방법은 보통 가감법을 많이 사용한다. 따라서 가감법을 사용해서 x와 y에 대한 식을 계산하면 다음과 같이 정리되고, 해당하는 값을 넣어주면 값이 나올 것이다. 답은 항상 정수이기 때문에 // 를 사용했다.

다른 방법으로는 방정식을 만족하는 해가 유일하게 하나 존재하고, -999~999 사이의 정수라는 조건이 있다. 따라서 반복문을 통해서 모든 값에 대해 체크를 하는 방식으로도 답을 구할 수 있다.

문제링크:

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

문제:

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력:

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2<=N<=5, 1<=B<=100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력:

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

풀이방법:

B의 최대 크기가 100,000,000,000인 만큼 효율적인 계산 방법이 필요한 문제다. 따라서 다음과 같은 규칙에 의해서 계산을 한다.

A^N일 때,

if N이 짝수라면, (A^2)^(N/2)로 수정한다.

if N이 홀수라면, (A^(N-1))*A로 수정하고, A는 answer에 곱한다.

N이 1이 될 때까지 위를 반복하고, 1이면 그 때의 A를 answer에 곱한다.

위와 같이 계산을 한다면 지수가 log2단위로 줄어들기 때문에 최대 100,000,000,000번 연산이 최대 36번으로 줄어들게 될 것이다. 

문제링크:

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

문제:

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 두면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p,q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하어야 한다.

입력:

암호 P(4<=P<=10^100)와 K (2<=K<=10^6)이 주어진다.

출력:

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

풀이방법:

 n보다 작은 소수를 찾아서 이를 P에다가 나눠본다. 이 때 나눠진다면 좋지 못한 암호이기 때문에 BAD와 그 수를 출력하면 된다. 이 때, K가 최대 10^6까지 가능하기 때문에 소수를 구하는 최적의 알고리즘이 필요할 것이라고 생각했고, 가장 효율적인 소수 알고리즘 중 하나인 에라토스테네스의 체를 사용했다.

 길이가 K이고 값들이 1인 배열을 만들었고, 에라토스테네스의 체를 사용해서 소수를 구했다. 에라토스테네스의 체를 간단히 설명하면 한 소수 n의 배수들은 이 소수 n로 다 나눠질 것이기 때문에 소수가 아니라는 것이다.

 따라서 해당하는 인덱스의 배열 값이 1이고, 소수라면 그 배수들의 배열값들을 다 0으로 만들어준다. 그리고 추후 탐색을 편하게 하기 위해서 인덱스를 answer 리스트에 담아둔다.

 이렇게 하면 answer에는 소수만 남게 되고, 이를 P에다가 나눠보면서 좋은 암호인지 판단한다.

문제링크:

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

문제:

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

입력:

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

출력:

테스트케이스마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다. (예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

풀이방법:

약수들을 찾는 것은 어렵지 않으나 출력 요건을 주의 깊게 맞춰야 하는 문제인 것 같다.

약수들을 찾는 것은 브루트포스 방법으로 2부터 다 나눠보면서 나머지가 없는 값을 찾으면 된다. 이 때, 조금이라도 시간을 줄이기 위해서 n까지 다 나눠보는 것이 아닌 n//2-1까지 나눠보도록 했다. 이렇게 약수들을 모두 찾은 다음에 중복을 제거한 다음에 정렬을 했다. (중복은 제곱수를 위해 제거, 9와 같은 경우 1,3,3과 같이 들어가 있을 것)

약수들의 합이 n과 같으면 완전수이므로 출력 조건에 맞춰서 출력을 하고, 다르면 n is NOT perfect.로 출력한다.

100,000미만의 완전수는 6, 28, 496, 8128만 있으니 확인 후 제출하면 된다.

문제링크:

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

문제:

2차원 배열이 주어졌을 때 (i,j) 위치부터 (x,y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i,j) 위치는 i행 j열을 나타낸다.

입력:

첫째 줄에 배열의 크기 N,M (1<=N,M<=300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1<=K<=10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i,j,x,y가 주어진다. (i<=x,j<=y).

출력:

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다.

풀이방법:

pypy3로 통과했습니다.

문제링크:

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

문제:

어떤 파일 시스템에는 디스크 공간이 파일의 사이즈와 항상 같지는 않다. 이것은 디스크가 일정한 크기의 클러스터로 나누어져 있고, 한 클러스터는 한 파일만 이용할 수 있기 때문이다.

예를 들어, 클러스터의 크기가 512바이트이고, 600바이트 파일을 저장하려고 한다면, 두 개의 클러스터에 저장하게 된다. 두 클러스터는 다른 파일과 공유할 수 없기 때문에, 디스크 사용 공간은 1024바이트가 된다.

파일의 사이즈와 클러스터의 크기가 주어질 때, 사용한 디스크 공간을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 파일의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 마지막 줄에는 클러스터의 크기가 주어진다. 이 값은 1,048,576보다 작거나 같은 자연수이다.

출력:

첫째 줄에 사용한 디스크 공간을 출력한다.

풀이방법:

파일을 클러스터에 넣으려고 할 떄 크게 3가지 경우가 발생한다.

1. 한 파일의 크기가 한 클러스터의 크기보다 큰 경우

2. 한 파일의 크기가 한 클러스터의 크기와 같은 경우

3. 한 파일의 크기가 한 클러스터의 크기보다 작은 경우

그리고 위 3가지 case는 몫과 나머지를 통해서 구할 수 있다.

파일사이즈를 클러스터의 크기로 나눴을 때, 몫이 1보다 커지게 된다면 1의 케이스에 해당하며 몫만큼 클러스터의 개수를 준비하고 나머지가 있을 경우 하나 더 준비하면 된다.

그리고 몫이 0이라면 나머지가 있을 경우에는 한 개를 준비하면 되고, 나머지가 없다면 준비안하면 된다.

몫과 나머지를 구할 수 있는 divmod를 사용해서 알고리즘을 구현하면 된다.

문제링크:

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