'전체 글'에 해당되는 글 185건

백준 - 단계별로 풀어보기 [2581] 

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

문제

숫자 M과 N을 받아서, M이상 N 이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에는 그 합을, 둘째 줄에는 최솟값을 출력하는 프로그램을 작성하는 문제이다. 이 때 소수가 없는 경우엔 -1을 출력한다.

풀이

에라토스테네스의 체를 활용하여 Max값 까지 존재하는 소수들을 모두 구하고, 합과 최솟값을 구하면 되는 문제이다.

에라토스테네스의 체를 개념을 구현하여 구하고자하는 소수 범위의 재곱근보다 작은 소수들의 배수들을 모두 지워나가다보면 마지막에 남는 수는 모두 소수라는 사실을 이용한 풀이 방식으로 접근하면 쉽게 풀이가 가능하다.

코드

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

int main() {
    int min,max,sum = 0;
    int min_value;
    bool prime[10000];
    fill_n(prime, 10000, 1);
    prime[0] = false;
    prime[1] = false;
    cin >> min;
    cin >> max;
    for (int i = 2; i <= sqrt(max); i++)
        if(prime[i] == true)
            for(int j = i*2; j <= max; j += i)
                prime[j] = false;

    for (int i = min; i <= max; i++)
        if(prime[i] == true)
        {
            if(sum == 0)
                min_value = i;
            sum += i;
        }
    if(sum == 0)
        cout << "-1";
    else
        cout << sum << '\n' << min_value;
    return 0;
}

평가

에라토스테네스의 체 개념을 모르는 사람에게는 다소 생소하고 어려울 수 있는 문제이다.

정답률은 39%지만 에라토스테네스의 체를 활용하기만 한다면 어렵지 않게  금방 풀 수 있다.

백준 - 단계별로 풀어보기 [1978] 

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

문제

1000이하의 자연수를 최대 100개 입력받은 후, 입력 받은 수 중 소수의 개수를 구하는 프로그램을 작성하는 문제이다.

풀이

우선 1000이하의 소수를 모두 구하는 것은 비효율적이므로, 각각의 숫자가 소수인지 아닌지를 판별하는것이 관건인 문제이다.

일반적인 접근 방법은 2보다 크고, 입력받은 수보다 작은 수까지를 모두 나눠보았을 때, 나눠지지 않으면 소수라고 판별하는 것이지만 보다 효율적이고 빠른 계산을 위해 에라토스테네스의 접근 방법을 사용한다.

에라토스테네스의 소수 필요충분조건은 2보다 크면서 자기 자신의 제곱근까지의 수에 나눠지지 않는 수이다.

즉 입력값의 재곱근까지 반복문을 돌려 소수 판별을 진행한다.

코드

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int num;
    cin >> num;
    int count = num;
    int input[100] = {0,};
    for(int i = 0; i < num; i++) {
        cin >> input[i];
        if (input[i] == 1)
            count--;
    }

    for(int i = 0; i < num; i++)
        for(int j = 2; j <= sqrt(input[i]); j++)
        {
            if(input[i] % j == 0)
            {
                count--;
                break;
            }
        }
    cout << count;
    return 0;
}

평가

난이도가 아주 쉬운 문제지만, 에라토스테네스의 접근 방법을 사용하면 보다 빠르게 풀 수 있는 문제이다.

백준 - 단계별로 풀어보기 [1011] 

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

문제

처음 이동 할 때 -1, 0 , 1 을 이동할 수 있는 우주선은, 항상 k광년 이동시마다 k-1, k, k+1 광년만큼만 다시 이동할 수 있다.

x지점에서 y지점으로 이동하려고 할 때 필요한 최소한의 공간 이동 횟수를 구하는 프로그램을 작성하는 문제이다.

도착 직전의 이동거리는 반드시 1광년으로 해야한다.

풀이

최대 범위가 2의 31승이므로 범위가 매우 크기 때문에 반복문으로 해결하려고 할 경우 시간초과가 발생하는 문제이다.

또한, int형이 표현할 수 있는 최대 범위를 넘어서므로 long long 자료형으로 변수를 선언해주어야한다.

먼저 이 문제의 규칙을 알아보자.

마지막에는 반드시 1광년을 이동해야 하므로, k광년 이동시, k-1, k, k+1광년만 이동할 수 있다는 제약 조건에 의해, 마지막 이동 전에는 최대 2광년 이동이 가능하다. 또한, 최대 2광년이므로, 그 이전의 이동은 최대 3광년까지만 가능하다.

이러한 규칙에 의해서 최대거리를 이동하기 위해서는,
1광년이동 -> 2광년이동 -> 1광년이동(마지막이동)

1광년이동 -> 2광년이동 -> 3광년이동 -> 2광년이동 -> 1광년이동(마지막이동)

의 규칙을 따라야 한다.

1 + 2 + 1 = 4(최대이동거리) = 2 X 2(최대 속도 N = 2), 이동 횟수 = 3번

1 + 2 + 3 + 2 + 1 = 9(최대이동거리) = 3 X 3(최대 속도 N=3), 이동 횟수 = 5번

1 + 2 + 3 + 4 + 3 + 2 + 1 = 16(최대이동거리) = 4 X 4(최대 속도 N=4), 이동 횟수 = 7번

의 규칙을 가지게 된다.

따라서 최소의 차원이동을 하기 위해서는 우선 최대 이동거리만큼 이동을 하고, 모자란 거리 만큼을 중간에 넣어주면 된다.

예를 들어

11광년을 이동해야 한다면 먼저 1 - 2 - 3 - 2 - 1 로 9광년을 이동한다고 가정 한 후, 아래와 같이 규칙을 어기지 않는 선에서 남은 2광년에 해당하는 수를 끼워넣어주면 된다.

1 - 2 - 3 - 2 - 2 - 1 즉 총 6번의 이동을 통해 이동 할 수 있다.

하지만 만약, 최대이동거리인 9광년을 이동한 후, 남은 광년이 최대 속도인  N = 3을 넘기는 경우에는 어떻게 해결할 수 있을까? 마찬가지로 13광년을 이동해야 할 경우, 1 - 2 - 3 - 2 - 1 로 9광년을 이동한다고 가정 한 후, 4광년 만큼을 끼워 넣어주면 된다.

1 - 2 - 3 - 3 - 2 - 1 - 1 혹은, 1 - 2 - 3 - 2 - 2 - 2 - 1 식으로 바꿔 총 7번의 이동을 통해 이동할 수 있다.

즉 남은 거리가 최대 이동 속도를 넘지 않으면 차원이동 한번을 추가하면 되고, 남은 거리가 최대 이동속도를 넘을 경우에는 

여러 번의 차원 이동을 추가하면 된다는 것이다.

여기서 도출해낼 수 있는 규칙은, 모든 입력값은 임의의 자연수 N과 A에 대해서N^2 + A 꼴로 표현할 수 있으며 이 때의 최소 차원 이동 횟수는 N^2 만큼을 이동하기 위한  (2N-1) 번의 이동 횟수와 (A / N) 의 올림값을 더한 수라는 것이다.

예를 들어 위의 경우에는 입력값이 13광년이었을 때, (3 X 3) + 4의 형식으로 표현이 가능하고, 이에 위 공식을 대입하면 처음 9광년을 이동하기 위해 (2 x 3 - 1), 즉 5번의 이동 횟수가 필요하고, 나머지 거리 (4 / 3) = 1.333이므로 올림값을 2만큼의 이동 횟수가 필요하다는 것이다.

cmath혹은 math.h 파일 안에 있는 ceil 함수를 통해 올림값을 구해 2N-1과 더해주는 코드를 작성하면 시간초과 없이 풀이가 가능하다.

코드

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main() {
    int num;
    scanf("%d",&num);
    for(int i = 0; i < num; i++)
    {
        long long x,y;
        long long move,max = 0;
        cin >>x>>y;
        while(max*max <= y-x)
            max++;
        max--;
        move = 2*max -1;
        long long rem = y-x - max*max;
        rem = (long long)ceil((double)rem / (double)max);
        move += rem;
        printf("%lld\n",move);
    }
}

평가

규칙을 도출해내는것이 간단하지 않은 문제이다. 마지막 이동 거리가 반드시 1이여야 한다는 것을 그냥 단순히 마지막은 1로 고정이라고 생각해서는 안되고, 1, 2, 3, 2, 1 꼴의 형태를 띄겠구나를 간파를 해야 규칙성을 알아낼 수 있는 문제이다.

단순 반복문으로는 무조건 시간초과가 발생하기 때문에, 해당 규칙을 알아내고 풀어야 한다.

또한 나머지 거리와 최대속도와의 관계를 분석하여 (A / N)의 올림값을 사용해야한다는 것을 도출을 해내야 문제 풀이가 가능하다. 대부분의 풀이가 코드만 덜렁 던져져 있어 이해를 끝까지 못하고 넘어가는 학생들이 많아, 글 주변은 없지만 최대한 상세히 풀이를 적어보았다. 

다소 까다로운 규칙성과 어려운 제약조건 떄문에 정답률이 27%인 고난도 문제이다.

못 풀었다고 하더라도 좌절하지 말고 설명을 차근차근 읽어보며 구현을 해보고 넘어가면 좋을 듯 하다.

백준 - 단계별로 풀어보기 [2775] 

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

문제

a층의 b호에 살려면 (a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 하는 아파트가 있다.

아파트는 0층부터 시작하며, 0층의 i호에는 i명이 산다.

Test Case의 개수와 층수 k, 호수 n이 주어질 때, 몇명이 살고 있는지를 출력하는 프로그램을 작성하는 문제이다.

풀이

먼저 호수는 최대 14호까지이므로, 15*14 이차원 배열을 생성한다.

그 후, 반복문을 통해 아파트의 주민수를 모두 구한다.

    for(int i = 0; i < 14; i++)
        people[0][i] = i+1;
    for(int i = 0; i < 14; i++)
    {
        for(int j = 0; j < 14; j++)
        {
            sum += people[i][j];
            people[i+1][j] = sum;
        }
        sum = 0;
    }

아파트의 주민수가 모두 구해진 후엔, 입력받은 층과 호수를 통해 바로 출력만 해주면 된다.

코드

#include <iostream>
using namespace std;

int main() {
    int num,sum = 0;
    cin >> num;
    int *k = new int[num];
    int *n = new int[num];
    int people[15][14] = {0,};
    for(int i = 0; i < 14; i++)
        people[0][i] = i+1;
    for(int i = 0; i < 14; i++)
    {
        for(int j = 0; j < 14; j++)
        {
            sum += people[i][j];
            people[i+1][j] = sum;
        }
        sum = 0;
    }
    for(int i = 0; i < num; i++)
    {
        cin >> k[i];
        cin >> n[i];
    }
    for(int i = 0; i < num; i++)
    {
        cout << people[k[i]][n[i]-1] << '\n';
    }
    return 0;
}

평가

이번 문제는 규칙성을 찾기보다는, 0층의 사람 수가 정해졌기 때문에, 아파트 전체의 모양을 먼저 구하고 찾는 것이 더 빠르다고 생각했다. 우선 층과 호수의 수가 14가 최대이기때문에, 연산시간이 초과가 될 가능성이 적었고 테스트 케이스가 여러개 이기 때문에 매번 계산을 하는것보다 오히려 아파트 호수 전체의 수를 미리 구하는것이 더 빠를 수도 있다고 가정하였다.

문제의 정답률은 58%로, 단순 반복문을 통한 해결이 가능한 문제이기 때문에 정답률이 낮지 않았던 것 같다.

백준 - 단계별로 풀어보기 [10250] 

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

문제

높이가 H, 호수가 W개 만큼 있는 호텔에서 손님에게 방을 배정하려고 한다. 손님들은 엘레베이터에서 가까운 호실을 선호하고, 거리가 같다면 더 밑 층을 선호한다. 이 때, N번째의 손님이 배정받는 방 번호를 구하는 프로그램을 작성하는 문제이다.

풀이

규칙성은 다음과 같다.

1번째 온 손님은 1층 101호,

2번째 온 손님은 2층 201호,

H번째 온 손님은 H층 H01호,

H+1번째 온 손님은 1층 102호,

...

2*H 번째 온 손님은 H층 H02호 꼴이다.

즉, H번째마다 호수가 한개씩 늘어나고, 1이 늘어날때마다 층이 한개씩 늘어나는 규칙성을 가지고 있다.

이를 활용하여 나머지 연산과 나누기 연산을 적절히 사용하여 코드를 작성하면 시간초과 없이 문제를 해결할 수 있다. 

코드

#include <iostream>
using namespace std;
int main() {
    int num,yy,xx;
    cin >> num;
    int *h = new int[num];
    int *w = new int[num];
    int *order = new int[num];
    for(int i = 0; i < num; i++)
        cin >> h[i] >> w[i] >> order[i];
    for(int i = 0 ; i < num; i++)
    {
        xx = order[i] / h[i] + 1;
        yy = order[i] % h[i];
        if(order[i] % h[i] == 0)
        {
            yy = h[i];
            xx--;
        }
        if(xx < 10)
            cout << yy << "0" << xx << '\n';
        else
            cout << yy << xx << '\n';
    }
}

평가

호실이 yyxx형태로 적혀있다는것을 고려하여 yy와 xx를 각각 구하는 방식으로 규칙성을 찾아가는 방법이 유효한 풀이 접근 방식이다. 만약 xx가 10보다 작을경우, 0을 중간에 끼워넣어줘야한다. (예를 들어 1층 첫호실은 11호가 아니라 101호이다.)

또한 층으로 나눠떨어지는 경우 yy는 무조건 층수와 같아지므로, 예외처리를 통해 풀이가 가능하다.

본 문제의 정답률은 35%로, yy와 xx를 구분하고 나머지 연산을 활용해야 하는 점, 각종 예외처리를 진행해야 한다는점에서 조금 까다로웠던 문제이다.

백준 - 단계별로 풀어보기 [2869] 

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

문제

낮에 A미터 올라가고, 밤에는 B 미터 미끄러지는 달팽이가 V미터를 오르는데에 걸리는 일자를 구하는 문제이다.

입력으로는 A,B,V를 입력받고, B는 반드시 A보다 작다.

풀이

이 문제도 반복문을 통해 높이를 오르려고 할 경우, V의 범위가 최대 1,000,000,000이므로 시간초과가 발생한다.

따라서, 몇일이 걸리는지를 수학적으로 식으로 구현하여야 한다.

정상에 일단 다다르기만 하면 미끄러지지는 않으므로, 최종적으로 가야하는 목표는 V가 아닌 V-A까지만 가면 다음날 아침에 A만큼 올라서 정상에 다다를 수 있다.

그리고 V-A를 가는데에 걸리는 기간은 (V-A)/(A-B)이다.

이때 (V-A) / (A-B)가 나머지가 0일 경우에는 (V-A) / (A-B) 일 만큼 오르고, 마지막날 A만큼 오르면 되지만,
(V-A) / (A-B)의 나머지가 0이 아닐 경우에는 정상에 도달하기에 이동거리가 조금 모자라므로 1을 추가로 더해주면 된다.

코드

#include <iostream>
using namespace std;
int main() {
    int a,b,v;
    cin >> a >> b >> v;
    int day = 1;
    day += (v-a)/(a-b);
    if((v-a)%(a-b) != 0)
        day++;
    if(a >= v)
        cout << "1";
    else
        cout << day;
    return 0;
}

평가

반복문을 사용할 경우 무조건 시간초과가 발생하는 문제이다.

목표점이 V가 아닌 V-A라는 것을 캐치하는것이 관건이고, 그 후 (V-A) % (A-B)를 활용하여 1을 더해줄지 안더해줄지를 결정하는 것이 정답으로의 접근 방법이다.

나머지 연산을 고려하지 못하는 경우가 많아 정답률이 27%인 다소 고난도 문제이다.

백준 - 단계별로 풀어보기 [1193] 

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

문제

위와 같은 지그재그로 순서를 할당하는 배열이 있다. 입력으로 순서 X가 주어졌을 때, X 번째 분수를 구하는 프로그램을 작성하는 문제이다.

풀이

규칙을 찾아서 풀어야 하는 문제이다. 1/1, 1/2, 2/1, 3/1, 2/2, 1/3 식으로 지그재그의 한 패턴당 1개, 2개, 3개식으로 늘어난다.

즉 입력받은 숫자가 몇번째 지그재그 패턴인지 먼저 찾아야 한다. 그 후, 해당 지그재그 패턴에서 몇번째 수인지를 알면 분수를 구할 수 있다.

짝수번째 패턴의 경우에는 1/i, 2/(i-1),3/(i-2), ..., i/1식으로 진행이 되고

홀수번째 패턴의 경우에는 i/1, (i-1)/2, (i-2)/3, ..., 1/i식으로 진행이 된다.

위와 같은 일반화된 공식을 활용하여 코드를 작성하면 반복문을 최소로 사용하면서 풀 수 있다.

코드

#include <iostream>
using namespace std;
int main() {
    int idx;
    cin >> idx;
    int i = 1;
    int diff = 0;
    for(int sum = 0; sum+i < idx; i++)
    {
        sum += i;
        diff = idx - sum;
    }
    if(i%2 == 1)
        cout << i-diff+1 << "/" << diff;
    else
        cout << diff << "/" << i-diff+1;
    return 0;
}

평가

반복문을 사용하면서 지그재그수를 하나하나 다 계산하다보면, 시간 초과가 발생하는 문제이다.

일반화된 규칙을 찾아내고, 주어진 변수를 활용하여 바로 계산하는 식으로 문제를 풀어야 한다.

백준 - 단계별로 풀어보기 [2292] 

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

문제

위 그림과 같은 방식으로 벌집의 주소가 정해질 때, 입력받은 방 주소 N은 벌집의 중앙 1번 방에서 몇 개의 방을 거쳐서 갈 수 있는지를 구하는 문제이다.

풀이

해당 문제도 마찬가지로 단순 반복문을 통한 계산 방식을 통해서는 시간 초과가 발생한다.

해당 방까지의 거리가 어떻게 되는지 규칙을 먼저 찾아야 한다.

2~7까지는 2번만에 이동이 가능하고,

8~19까지는 3번만에 이동이 가능하고,

20~38까지는 4번만에 이동이 가능하다.

규칙성은 간단하다, 바깥층으로 나갈 때 마다, 6,12,18,24,30,36식으로 6*Layer식으로 범위가 늘어난다.

이를 활용하여, 6*i의 등비수열의 합을 구하고, 그 합이 입력된 주소보다 크게끔 하는 i를 찾아서 출력해주면 된다. 

코드

#include <iostream>
using namespace std;
int main() {
    int number;
    cin >> number;
    int i = 0;
    for(int sum=2; sum <= number; i++)
        sum += 6*i;
    if(number == 1) i=1;
    cout << i;
    return 0;
}

평가

규칙을 찾아내고, 등비수열의 합을 활용하는 접근을 할 경우 쉽게 해결할 수 있으나, 규칙을 못 찾게되면 막연한 반복문으로 인해 시간초과가 발생하는 문제이다. 수학 1 카테고리의 문제들은 대부분 규칙성을 찾아야 하는 문제들이기 때문에 단순 반복문으로는 해결할 수 없다는 사실을 감안하고 풀이를 진행하는 것이 좋다.

백준 - 단계별로 풀어보기 [2839] 

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

문제

설탕의 무게 N을 입력받고, 3kg짜리 봉지와 5kg 짜리 봉지를 섞어서 가져가는 경우의 수 중, 가장 최소 개수의 봉지를 구하는 문제이다.

풀이

결국 최소의 봉지를 들고가려면, 5kg짜리 봉지를 최대한 많이 활용하여야 하기 때문에, 설탕의 무게 N을 먼저 5로 나눠 본 후에, 3으로 나눠 떨어진다면 바로 정답 출력, 아니라면 5kg 봉지를 한 개씩 줄여나가면서 최소 개수의 봉지를 구하면 된다.

코드

#include <iostream>
using namespace std;
int main() {
    int kg;
    cin >> kg;
    int a,b;
    a = kg/5;
    while(1)
    {
        if(a < 0)
        {
            cout << "-1";
            return 0;
        }
        if((kg-(5*a))%3 == 0)
        {
            b = (kg-(5*a))/3;
            break;
        }
        a--;
    }
    cout << a+b;
    return 0;
}

평가

대표적인 Greedy Algorithm류 문제이다. 5kg으로 먼저 나눠가면서 3kg 봉지의 수를 늘려나가는 식의 방식을 고안만 할 수 있다면 쉽게 풀 수 있는 문제였을 것이지만, 그리디 알고리즘을 처음 접해보는 사람들에게는 다소 막막할 수 있는 문제이다. 정답률은 30%로 생각보다 아주 낮은 정답률을 가지고 있다.

백준 - 단계별로 풀어보기 [1712]

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

문제

고정 비용 A와 노트북 한대를 생산하는데에 필요한 가변 비용 B 그리고 노트북 판매 가격 C를 입력받고, 손익분기점을 구하는 문제이다. 손익분기점이 발생하지 않는 경우에는 -1을 출력하면 된다.

풀이

단순히 해결 할 수 있는 문제이다. 오히려 반복문등을 활용한 풀이를 할 경우 시간초과가 발생할 수 있다.

결국 구해야하는 값은, 노트북 생산 단가 B와 판매 가격 C를 고려했을때 몇대를 팔아야 고정비용을 넘길 수 있느냐이기 때문에,

A / (C-B)에 1을 더한값이 구하고자 하는 값이다.

코드

#include <iostream>
using namespace std;
int main() {
    int a,b,c;
    cin >> a >> b >> c;
    int profit = 0;
    int cost = 0;
    if(c <= b)
    {
        cout << "-1";
        return 0;
    }
    cout << a/(c-b) + 1;
    return 0;
}

평가

수식을 활용하지 않고, 다른 방법으로 풀이하게 될 경우 시간 초과가 발생하도록 설계된 문제이다.

문제를 단순히 Brute Force방식으로 해결하려고 하지 말고, 최대한 규칙과 점화식을 찾아 낸 후 단번에 계산하는 방법을 알아 내야 한다.