개발 블로그

문제 링크 : 

www.acmicpc.net/problem/17427

문제

두 자연수 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)를 출력한다.

접근 방법 1

직관적으로 풀었더니 제한시간인 0.5초를 넘어서 시간초과가 떴다. f(1)부터 f(N)까지 하나씩 구해서 더하는 방식으로 짜면 안되는 것 같다.

#include <iostream>

using namespace std;


int main(){
    
    int N, ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=i; j++){
            if(i%j == 0) ans +=j;
        }
        
    }
    
    cout << ans << "\n";
    
    return 0;
}

접근방법 2

새로운 접근 방법으로 풀어보았다.

N = 10 일때를 보자.

f(1) = sum(1)

f(2) = sum(1, 2)

f(3) = sum(1, 3)

f(4) = sum(1, 2, 4)

f(5) = sum(1, 5)

f(6) = sum(1, 2, 3, 6)

f(7) = sum(1, 7)

f(8) = sum(1, 2, 4, 8)

f(9) = sum(1, 3, 9)

f(10) = sum(1, 2, 5, 10)

이고 약수의 숫자들을 카운팅해보면, 

1 : 10개 (10을 1로 나눈 몫)

2 : 5개(10을 2로 나눈 몫)

3 : 3개(10을 3으로 나눈 몫)

4 : 2개(10을 4로 나눈 몫)

.

.

.

.

10: 1개(10을 1로 나눈 몫)

과 같이 규칙이 있음을 알 수 있다.

주의)

또한 처음에는 ans 변수를 int 형으로 선언했는데 오류가 났었다. 입출력 예시 자료를 보니 출력값이 82256014였고 이를 이진수로 변환하면 100111001110010000010001110(27비트)로 4바이트를 넘어가서 오류가 나는 거였다. 8바이트인 long long (int생략 가능) 으로 바꿔주니 정답처리가 되었다. 자료형에도 주의하자!!

#include <iostream>
using namespace std;

int main(){
    
    
    int N;
    long long ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        ans += (N/i)* i;
    }
    
    cout << ans << "\n";
    
    return 0;
}

문제 링크 : 

www.acmicpc.net/problem/1037

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

접근 방법

N의 진약수 중 크기순으로 나열했을 때, 가장 작은 약수와 큰 약수를 곱하면 N이 나온다는 사실을 이용했다. 

진약수들을 입력받을 때, 크기순으로 입력이 들어오지 않는다는 점을 주의하자!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> vec;

int main(){
    
    int cnt, ans;
    cin >> cnt;
    
    for(int i = 0; i<cnt; i++){
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    
    sort(vec.begin(), vec.end());
    ans = vec[0] * vec[cnt-1];

    cout << ans << "\n";
    
    return 0;
}