1주차 - 시작은 아무거나

[접기]

목차

  • 1. 개요
  • 2. 이론
  • 3. 문제와 풀이
    • 3.1. 1850번: 최대공약수
    • 3.2. 2840번: 행운의 바퀴
    • 3.3. 3613번: Java vs C++
    • 3.4. 11658번: 구간 합 구하기 3
    • 3.5. 3190번: 뱀
    • 3.6. 1328번: 고층 빌딩
    • 3.7. 2410번: 2의 멱수의 합
    • 3.8. 2014번: 소수의 곱
    • 3.9. 13334번: 철로
    • 3.10. 14464번: 소가 길을 건너간 이유 4
    • 3.11. 1017번: 소수 쌍
    • 3.12. 1459번: 걷기
    • 3.13. 2829번: 아름다운 행렬
    • 3.14. 10830번: 행렬 제곱


1. 개요


일단 뭐라도 시작해야 진행이 될 것 같아서 아무 문제나 넣어봤습니다.

2. 이론


아무 문제나 고른거라 특별히 정리할만한 이론은 없습니다. 다음 주부터 이론을 진행할 예정입니다.

3. 문제와 풀이


3.1. 1850번: 최대공약수


게시판 글 바로가기
1850번: 최대공약수

[틀:접힌글 시작(제목=풀이 보기, 종류=정보)]
모든 자리가 {{{1}}}로만 구성된 수를 두 개 주고, 이들의 최대공약수를 구하는 문제입니다. 모든 자리가 {{{1}}}로만 구성되었다는 것은 {{{111}}}, {{{1111}}}, {{{11111}}}과 같이 {{{1}}}만 주욱 늘어놓은 숫자들이라는 의미입니다. 숫자가 매우 길어질 수 있으므로 실제론 각 숫자의 자릿수만을 입력으로 줍니다. 예를 들어, 첫 번째 예제 입력인 {{{3 4}}}는 {{{111}}}과 {{{1111}}}의 최소공배수를 찾으라는 의미입니다.

수가 작다면 원래 숫자로 복원한 뒤에 일반적인 최대공약수 구하는 방법을 사용할 수 있습니다. 최대공약수는 일단 {{{gcd(a, b)}}}라는 함수를 통해 구할 수 있다고 가정해봅시다. 그렇다면 다음과 같은 코드를 작성해볼 수 있습니다. 코드는 통일성을 위해 C++로 작성하였습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int real_a = 0, real_b = 0;
for (int i = 0; i < a; i++)
real_b = real_a * 10 + 1;
for (int i = 0; i < b; i++)
real_b = real_b * 10 + 1;
int ans = gcd(real_a, real_b);
printf("%d", ans);
return 0;
}

그러나 수가 작다고 하더라도 {{{real_a}}}와 {{{real_b}}}를 구하는 과정은 약간 비효율적으로 느껴집니다. {{{1}}}로만 구성된 숫자들은 누가 봐도 규칙적이므로 무언가 수식을 통해 나타낼 수 있지 않을까하는 생각을 해볼 수 있습니다. 사실 모든 숫자들에 {{{9}}}를 곱해보면 좀 더 명확하게 식으로 나타내어질 법한 규칙이 보입니다.
{{{n}}} {{{1}}}이 {{{n}}}개 {{{x9}}} {{{10n}}}
{{{1}}} {{{1}}} {{{9}}} {{{10}}}
{{{2}}} {{{11}}} {{{99}}} {{{100}}}
{{{3}}} {{{111}}} {{{999}}} {{{1000}}}
{{{4}}} {{{1111}}} {{{9999}}} {{{10000}}}
{{{5}}} {{{11111}}} {{{99999}}} {{{100000}}}
{{{...}}} {{{...}}} {{{...}}} {{{...}}}
즉, {{{1}}}이 {{{n}}}개 있는 수는 {{{(10n-1)/9}}}이라는 것을 알 수 있습니다. 이를 이용해 방금 짠 프로그램을 조금 더 빠르게 바꿔봅시다. {{{pow(a, n)}}}이라는 함수 또한 미리 만들어져 있다고 가정합시다. 실제로 {{{an}}}은 {{{O(log n)}}}시간 내에 구할 수 있습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int pow(int a, int n) {
// pow 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int real_a = (pow(10, a) - 1) / 9;
int real_b = (pow(10, b) - 1) / 9;
int ans = gcd(real_a, real_b);
printf("%d", ans);
return 0;
}

그러나 이는 여전히 느린 방법입니다. 여기에 10의 거듭제곱을 미리 전처리 해두거나 해서 아무리 거듭제곱을 빠르게 계산하더라도 결국 최소공배수를 구하는 데 매우 오랜 시간이 걸립니다. 왜냐하면 입력으로 주어지는 수가 {{{2^63}}}까지인데, 그렇다는 말은 실제로 주어지는 수는 상상하기 힘들 정도로 커진다는 것입니다.

그런데, 사실 우리가 실제로 주어진 수들을 식으로 표현했으니 두 수의 최대공약수까지 수학으로 계산해버리면 됩니다. 실제로, 두 수의 최대공약수 또한 {{{(10n-1)/9}}} 꼴이어야 한다는 것은 쉽게 증명할 수 있습니다. 그러면 {{{(10a-1)/9}}}이 {{{(10b-1)/9}}}를 나눈다는 것과 {{{a}}}이 {{{b}}}를 나눈다는 것이 동치라는 것까지 증명할 수 있습니다. 따라서 그냥 주어진 {{{a}}}와 {{{b}}}의 최대공약수가 {{{d}}}라면 우리는 {{{(10d-1)/9}}}, 즉, {{{d}}}개의 {{{1}}}을 출력하면 됩니다. 코드로 나타내면 다음과 같습니다.


#include

int gcd(int a, int b) {
// gcd 구현
return ???;
}

int main() {
int a, b;
scanf("%d %d", &a, &b);
int d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}

그러나 여기에서 하나 주의할 점은 입력이 {{{int}}}범위를 벗어날 수 있다는 것입니다. 따라서 {{{long long}}}을 사용해야 모든 테스트케이스를 통과할 수 있습니다.


#include

long long gcd(long long a, long long b) {
// gcd 구현
return ???;
}

int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}

실제로 {{{gcd(a, b)}}}의 구현까지 포함한 예시 정답 코드는 다음과 같습니다.


#include

long long gcd(long long a, long long b) {
long long t = 1;
while b != 0:
t = a % b;
a = b;
b = t;
return a;
}

int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long d = gcd(a, b);
for (int i = 0; i < d; i++)
printf("1");
return 0;
}
[틀:접힌글 마침]

3.2. 2840번: 행운의 바퀴



3.3. 3613번: Java vs C++



3.4. 11658번: 구간 합 구하기 3



3.5. 3190번: 뱀



3.6. 1328번: 고층 빌딩



3.7. 2410번: 2의 멱수의 합



3.8. 2014번: 소수의 곱



3.9. 13334번: 철로



3.10. 14464번: 소가 길을 건너간 이유 4



3.11. 1017번: 소수 쌍



3.12. 1459번: 걷기



3.13. 2829번: 아름다운 행렬



3.14. 10830번: 행렬 제곱