개발 블로그

문제 링크 : www.acmicpc.net/problem/1748

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

접근 방법 

입력받은 N을 10, 100, 1000으로 나눈 몫에 따라 경우를 나누어 생각해준다.

case 1) 몫 q가 0보다 클 때는 1~9, 10~99, 100~999과 같이 full로 자리수를 카운팅해준다.

case 2) q가 0이 되면 10~N, 100~N, 1000~N 과 같이 N까지 끊어서 자리수를 카운팅해준다.

예를 들어 N=120일때를 보자.

x = 1일 때, 120/10^1 = 12이므로 0보다 크고 따라서 1~9까지 쭉 썼을 때 자리수는 9개이다. (9 = (10^x  - 10^x-1) * 1)

x = 2일때, 120/10^2 = 1이므로 0보다 크고 따라서 10~99까지 쭉 썼을 때 자리수는 (99-10 + 1) * 2 개이다. 

x = 3일때, 120/10^3 = 0이므로, 이때는 999까지 쓰기 전에 N이 나오기 때문에 100~120까지 썼을 때 자리수는 (120-100+1) * 3 개이다.

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    
    
    int N;
    cin >> N;
    int x = 1;
    int ans = 0;
    while(1){
    
        int q = N/pow(10,x);
        if(q>0){
            ans += (pow(10,x)-pow(10,x-1)) * x;
        }
        else{
            ans += (N-pow(10,x-1) + 1) * x;
            break;
        }
        x++;
    }
    
    cout  << ans << "\n";

    return 0;
}

문제 링크 : www.acmicpc.net/problem/1476

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 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이기 때문에, 정답이 음수가 나오는 경우는 없다.

접근 방법 1

num을 1부터 하나씩 증가시키면서 나머지가 각각 입력값 e, s, m 과 일치하는지 비교했는데 시간초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num= 1;
    while(1){
        
        if(num%15 == e && num%28 == s && num%19 == m){
            break;
        }
        else num++;
        
    }
    
    cout << num << endl;
    
    return 0;
}

접근 방법 2

num을 1부터 증가시키는 것이 아니라 28의 배수를 기준으로 증가시키면서, num을 15와 19로 나눈 나머지를 입력값과 비교했다. 28의 배수로 한 이유는 15와 19보다 28이 크기 때문에 계산량을 줄이기 위함이다. 그러나 또 시간 초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
        
        
    }
    
    
    cout << num << "\n";
    
    return 0;
}

1,2번 시간초과 난 이유

참고:www.acmicpc.net/board/view/51295

입력이 15,28,19 일때를 생각해보자. 즉 e = 15, s = 28, m = 19일때 (num%15)의 범위는 0~14이므로 절대로 15(e)가 될 수 없다. 마찬가지로 (num%19)의 범위는 0~18이므로 절대로 19(m)이 될 수 없어서 계속 반복문을 도는 것이다.

그래서 아래와 같이 28의 배수를 기준으로 할 때, 반복문 시작 전에 if 문으로 e와 m을 체크해주면 시간초과가 뜨지 않는다. 이때 주의할 점은 s에 대해서 검사하면 아예 틀린 값이 나온다. (이유 : 입력이 15, 28, 19이면 출력이 0이 나온다!)

#include <iostream>

using namespace std;


int main(){

    int e,s,m;
    cin >> e >> s >> m;
    
    if(e>=15) e = e%15;
    if(m>=19) m = m%19;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
    }
    
    cout << num << "\n";
    
    return 0;
}

접근 방법 3

num을 1부터 하나씩 증가시키면서 num - e를 15로 나눈 값이 0인지를 판단하고, s와 m에 대해서도 같은 방법으로 비교하여 3조건이 모두 0이면 반복문을 멈춘다.

예를 들어,

num = 5266, e = 1, s = 2, m = 3 일 때,

5266 = 15*351 + 1

5266 = 28*188 + 2

5266 = 19*277 + 3 

이므로 각 나머지를 LHS로 이항해서 15,28,19 로 나눈 나머지가 모두 0일 때 반복문을 멈춘다.

위의 방법과 어떤 점에서 다른지 모르겠지만 아래 방법은 시간초과가 나지 않았다. 

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num = 1;
  
    while(1){
        
        if((num-e)%15 == 0 && (num-s)%28==0 && (num-m)%19 == 0){
            break;
        }
        else num++;
        
    }
    
    
    cout << num << "\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;
}