졍's 기술 블로그

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론

약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입출력

우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.

처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.

num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.

#include <iostream>
#include <string>
using namespace std;

int cal_len(long long n){
    string num = to_string(n);
    return num.length();
}

long long ispossible(int n){
    // n의 길이 계산
    int len = cal_len(n);
    string num;
    // n의 길이만큼 1로만 구성된 문자열 만들기
    for(int i=0;i<len;i++){
        num += '1'; // O(n)으로 동작
    }
 
    while(true){
        // num이 n의 배수인지 확인
        if(num%n==0) return num.length();
        // num 한 자리 추가
        num += '1';
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 런타임 에러(out_of_range)로 실패 ㅠ

num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.

그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.

결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.

Algorithm

Brute Force
1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음
2. num이 n으로 나누어 떨어지는지 확인
    2-1. 나누어떨어지면 num의 길이 return
    2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산)
            → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !

Code

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num의 크기 줄여주기
        num%=n;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

메모리: 2020 KB
시간: 0 ms

소수

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 정수론, 소수 판정

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입출력

Code

# 입력
M = int(input())
N = int(input())

# 소수 찾기
sum_ = 0
min_ = 10000
for i in range(M, N+1):
    count = 0
    if i > 1 and i < 4: # i가 2 또는 3인 경우 소수로 판별
        sum_ += i
        if min_ > i:
            min_ = i
    else: # 그 외의 숫자인 경우
        for j in range(2, i//2 + 1): # 2 ~ i의 절반에 해당하는 숫자까지로 i를 나눠봄
            if i % j == 0: # 나누어 떨어지면 더이상 검사하지 않고 다음 숫자 확인
                break
            else: # 나누어 떨어지지 않는 경우 몇 번 나누어 떨어지지 않았는지 Count
                count += 1
        if count == i//2 - 1: # 나누어 떨어지지 않은 횟수가 j for문을 돈 횟수와 같다면
            sum_ += i # 소수로 판별
            if min_ > i:
                min_ = i
            
if sum_ > 0:
    print(sum_)
    print(min_)
else:
    print(-1)

메모리: 30860 KB
시간: 480 ms

날짜 계산

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 4 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론, 중국인의 나머지 정리

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입출력

Algorithm

1. 현재 시간 1 증가
2. e, s, m 1 증가
    ☞ 각각 15, 28, 19를 넘으면 1로 초기화

Code

E, S, M = map(int, input().split())

e, s, m = 0, 0, 0
time = 0
while True:
    time += 1
    
    if e == 15:
        e = 1
    else:
        e += 1
        
    if s == 28:
        s = 1
    else:
        s += 1
        
    if m == 19:
        m = 1
    else:
        m += 1
        
    if e == E and s == S and m == M:
        break

print(time)

메모리: 30860 KB
시간: 72 ms

골드바흐의 추측

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

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."을 출력한다.

예제 입출력

Algorithm

1. 아레토스테네스의 체를 이용해 입력된 값 중 MAX값을 기준으로 소수 리스트 생성
2. 입력받은 값보다 작은 홀수인 소수로 해당 값을 만들 수 있는지 확인

Code

import sys
import math
input = sys.stdin.readline

nums = []
while True:
    num = int(input())
    if num == 0:
        break
    nums.append(num)

# 에라토스테네스의 체를 이용해 MAX(입력값)를 기준으로 소수 리스트 생성
MAX = max(nums)
prime = {}
for i in range(MAX+1):
    prime[i] = True
prime[1] = False
for i in range(2, int(math.sqrt(MAX + 1))):
    if prime[i]:
        for j in range(i*2, MAX, i):
            prime[j] = False

# 입력받은 수보다 작은 홀수 소수로 해당 값을 만들 수 있는지 확인
answer = ''
for i in nums:
    for j in range(i-3, 0, -2):
        if prime[j] and prime[i - j]:
            answer += str(i) + ' = ' + str(i-j) + ' + ' + str(j) + '\n'
            break
    if j == 1:
        answer += 'Goldbach\'s conjecture is wrong.\n'
print(answer)

메모리: 118412 KB
시간: 704 ms

소수 구하기

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론,소수 판정, 에라토스테네스의 체

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입출력

Algorithm

1. 1부터 N까지 숫자 리스트 생성
2. 2부터 루트 N까지의 숫자로 리스트 내의 숫자를 순차적으로 나누면서 나누어떨어지는 수 Fasle 표시
3. M부터 N까지의 숫자 중 True 값 갖는 숫자만 출력

Code

import math

# 입력
M, N = map(int, input().split())
# 1부터 N까지 숫자 리스트 생성
nums = [True for _ in range(N+1)]
nums[1] = False # 1은 소수가 아니므로 False 저장

# 2부터 루트 N + 1까지의 숫자로 나눔
for i in range(2, int(math.sqrt(N) + 1)):
    # 현재 숫자가 나누어진 적 없다면
    if nums[i]:
        # i * 2부터 N을 넘지 않을 때까지의 숫자를 모두 Fasle로 저장
        j = 2
        while i*j < N+1:
            nums[i*j] = False
            j += 1

answer = ''
for i in range(M, N+1):
    if nums[i]:
        answer += str(i) + '\n'
print(answer)

메모리: 42080 KB
시간: 684 ms

약수의 합 2

티어 : Silver 2
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제 입출력

Algorithm

N까지의 약수 중 i라는 숫자는 N//i개 존재
-> i가 1부터 N까지 증가하면서 i의 개수 * i 더하기

Code

N = int(input())
sum_ = 0
for i in range(1, N+1):
    sum_ += i * (N//i)
print(sum_)

메모리: 30864 KB
시간: 240 ms

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입출력

Code

while True:
  try:
    n = int(input())
    num = 1
    while True:
      if int('1'*num) % n == 0:
        print(len('1'*num))
        break
      num += 1
  except:
    break

메모리: 30860 KB
시간: 2240 ms