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

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

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

문제

0부터 20 사이의 n이 주어졌을 때, n번째 피보나치 수열의 수를 출력하는 문제이다.

풀이

결국 피보나치 수열의 n번째 값은

n-2번째 피보나치 수열의 값 + n-1번째 피보나치 수열의 값이므로, 재귀를 통해 풀이가 가능하다.

코드

#include <cstdio>
int fibo(int num) {
    if(num == 0)
        return 0;
    if(num == 1)
        return 1;
    return fibo(num-2) + fibo(num-1);
}
int main() {
    int num;
    scanf("%d",&num);
    printf("%d",fibo(num));
}

평가

재귀의 기본이라고 할 수 있는 피보나치 수열 문제이다.

딱히 신경써야 할 부분은 없어서, 정답률이 70%로 높은 편이다.

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

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

문제

0부터 12사이의 수 N의 팩토리얼을 구하는 문제이다.

풀이

factorial의 정의에 따라서 재귀함수로 구현하기 위해서는,

int factorial(int n)
{
    if(n <= 1)
        return 1;
    return n * factorial(n-1);
}

위와 같은 소스코드로 구현이 가능하다.

이 때, 조건을 n <= 1로 하는 이유는 입력이 0부터이기 때문에, 만약 n == 1로 할 경우, 무한루프에 빠져 시간초과가 발생한다.

만약 재귀로 풀었는데 시간초과 에러가 뜨는 경우는 조건문을 위처럼 수정해야 한다.

코드

#include <cstdio>

int factorial(int n)
{
    if(n <= 1)
        return 1;
    return n * factorial(n-1);
}

int main() {
    int num;
    scanf("%d",&num);
    printf("%d",factorial(num));
}

평가

n <= 1 조건을 n == 1로 하여 시간초과가 많이 발생하는 문제이다.

항상 입력값의 조건을 유의하며 문제를 풀이하는 습관을 들여야 한다.

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

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

문제

A라는 사람의 좌표 x1,y1과 B라는 사람의 좌표 x2,y2 그리고 임의의 좌표 C에 대하여 A로부터의 거리 r1와 B로부터의 거리 r2를 입력받았을 때 존재할 수 있는 C의 개수를 출력하는 문제이다.

풀이

이 문제는 사실 중학교 수학을 알아야 풀 수 있는 내용이다.

원의 정의란, 한 점에서 일정한 거리만큼 떨어진 점들의 집합이다.

따라서 A좌표에서 거리가 r1일 수 있는 C들의 집합은 A좌표를 중심으로하고 반지름이 r1인 원의 형태를 가지고 있으며, 

B좌표에서 거리가 r2일 수 있는 C들의 집합은 B좌표를 중심으로 하고 반지름이 r2인 원의 형태를 가지고 있다.

즉 이때, 존재할 수 있는 C들의 개수는 이러한 두 원의 접점의 개수를 의미한다.

위와 같은 접근에서 알 수 있는 사실은 두 점 사이의 거리의 따라 답이 결정된다는 것이다.

가능한 경우의 수는 다음과 같다.

d = r1 + r2 일 때, 두 원은 접하고 있으므로 가능한 C는 1개

r1 - r2 < d < r1 + r2 일 경우, 두 원은  두 점에서 접하므로 가능한 C는 2개

그 외의 경우에는 접하지 않으므로 가능한 C는 0개이다.

코드

#include <iostream>
using namespace std;
int main() {
    int x1,y1,r1,x2,y2,r2,d,cond1,cond2,num;
    cin >> num;
    for(int i = 0; i < num; i++)
    {
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        d = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
        cond1 = (r1-r2) * (r1-r2);
        cond2 = (r1+r2) * (r1+r2);
        if(d == 0)
        {
            if(cond1 == 0)
                cout << "-1" << '\n';
            else
                cout << "0" << '\n';
        }
        else if (d == cond1 || d == cond2)
            cout << "1" << '\n';
        else if (cond1 < d && d < cond2)
            cout << "2" << '\n';
        else
            cout << "0" << '\n';
    }

}

평가

두 원의 위치관계에 대한 개념을 깨닫고 풀 경우 쉽게 풀 수 있으나, 이를 생각하지 못하면 다소 풀이가 막막한 문제이다.

정답률은 19.474%로 매우 어려운 문제로 분류된다.

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

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

문제

택시 기하학에서 반지름 R이 주어졌을 때,

일반적인 유클리드 기하학에서의 원의 넓이와 택시 기하학에서의 반지름이 R인 원의 넓이를 출력하는 문제이다.

풀이

택시 기하학에서의 원은 마름모 형태를 가지고 있다.

위와 같은 형태가 택시 기하학에서의 원이다.

한점에서의 거리가 같은 점들의 집합을 모두 이으면 위와 같은 마름모꼴이 된다.

따라서, 정사각형의 한변의 길이는 sqrt(2)*r이 된다.

따라서 유클리드 기하학에서의 원의 넓이는 r*r*M_PI이고, 

택시 기하학에서의 원의 넓이는 r*r*2로 정의할 수 있다.

코드

#include <cstdio>
#include <cmath> //M_PI 사용 위함
#define _USE_MATH_DEFINES // cmath에 정의된 상수 사용하겠다는 의미
int main() {
    double r,s1,s2; // float형으로 풀 경우 정밀도 문제로 오답발생함.
    scanf("%lf",&r);
    s1 = M_PI * r * r;
    s2 = r*r*2;
    printf("%.6f\n",s1);
    printf("%.6f\n",s2);
    return 0;
}

평가

택시 기하학에서의 원이 정사각형 모양이라는 것을 금방 간파할 수 있다면 풀이가 가능한 문제이다.

또한, 만약 본 문제를 해결하기 위해서 float 자료형을 사용한다면, 오차 0.0001을 만족하지 못하는 경우가 발생하여 반드시 double 자료형으로 문제를 푸는 것이 좋다.

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

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

문제

삼각형의 변 길이를 입력받고 직각삼각형인지 아닌지 판단하고 맞으면 right, 아니면 wrong을 출력하는 프로그램을 작성하는 문제이다.

풀이

입력받은 변중, 가장 큰 값을 가진 변의 재곱값이 나머지 두 변의 재곱값의 합과 같은지 판별

코드

#include <iostream>
using namespace std;

int main() {
    int a,b,c;
    int greatest;
    while(1)
    {
        cin >> a >> b >> c;
        if(a == 0)
            break;
        if(max(a,b) == a)
            if(max(a,c) == a)
            {
                if(a*a == b*b + c*c)
                    cout << "right" << '\n';
                else
                    cout << "wrong" << '\n';
            }
            else
            {
                if(c*c == a*a + b*b)
                    cout << "right" << '\n';
                else
                    cout << "wrong" << '\n';
            }
        else
            if(max(b,c) == b)
            {
                if(b*b == a*a + c*c)
                    cout << "right" << '\n';
                else
                    cout << "wrong" << '\n';
            }
            else
            {
                if(c*c == a*a + b*b)
                    cout << "right" << '\n';
                else
                    cout << "wrong" << '\n';
            }
    }
}

평가

조건문을 활용하여 피타고라스의 정리를 만족하는지를 살피면 풀 수 있는 문제이다.

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

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

문제

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해 필요한 네번째 점을 찾는 프로그램을 작성하는 문제이다.

풀이

직사각형의 나머지 점을 찾기 위해서는 아주 간단한 로직을 따르면 된다.

x축과 y축을 기준으로 반드시 쌍을 이루고 있다는 규칙이다.

예를 들어, (30, 20) (10, 10) (10, 20)이 주어진 위 문제에서는 (10, 10) (10, 20) (30, 20) 이렇게 10,10 20,20이 짝을 이뤘고, 

쌍을 만족시키기위해서 새롭게 들어가야하는 수는 (30, 10)이다. (10, 10) (10, 20) (30, 20) (30, 10) 

이러한 규칙을 활용하여, 쌍을 이루지 못한 좌표의 x값과 y값을 가지는 좌표를 출력하면 쉽게 풀이가 가능하다.

코드

#include <iostream>
using namespace std;

int main()
{
    int x[3];
    int y[3];
    for(int i = 0; i < 3; i++)
        cin >> x[i] >> y[i];
    if(x[0] == x[1])
        cout << x[2] << " ";
    else if(x[0] == x[2])
        cout << x[1] << " ";
    else
        cout << x[0] << " ";

    if(y[0] == y[1])
        cout << y[2];
    else if(y[0] == y[2])
        cout << y[1];
    else
        cout << y[0];
}

평가

정답률 76%의 아주 쉬운 문제이다.

if 문을 활용하여 풀이가 가능하다.

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

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

문제

높이 h, 길이 w의 직사각형이 주어졌을 때, 직사각형 안의 임의의 점 x,y에서 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하는 문제이다.

풀이

왼쪽 아래 꼭지점이 (0,0)이므로, 직사각형의 아래쪽 경계선은 x축, y축이다.

따라서 아래쪽 경계선 까지의 거리는 각각 x와 y이며 위쪽 경계선까지의 거리는 w-x와 h-y이다.

따라서 이중에서 최소값을 출력하면 되는 문제이다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int x,y,w,h;
    int tmp1,tmp2;
    cin >> x >> y >> w >> h;
    tmp1 = min(x,y);
    tmp2 = min(w-x,h-y);
    cout << min(tmp1,tmp2);
}

평가

min함수를 활용하면 쉽게 풀 수 있는 문제이다.

정답률은 58%로 별도의 예외처리등이 없어 평이한 난이도를 가지고 있다고 생각된다.

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

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

문제

2보다 큰 짝수 n이 주어졌을 때, 가장 작은 차이가 나는 두 소수의 합으로 표현을 하려고 한다. 이 때 두 소수를 구하고 출력하는 프로그램을 작성하는 문제이다.

풀이

에라토스테네스의 체를 이용하여 소수 판별 배열을 만들고, N/2를 중심으로, N/2 - i과 N/2 + i 모두가 소수가 되도록 하는 i의 값을 찾고, N/2 - i 와 N/2 + i의 값을 출력하면 쉽게 해결할 수 있다.

코드

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int num, max = 0;
    cin >> num;
    int* even = new int[num];
    for(int i = 0; i < num; i++) {
        cin >> even[i];
        if(even[i] > max)
            max = even[i];
    }
    bool *prime = new bool[max+1];
    fill_n(prime, max + 1, 1);
    prime[0] = false;
    prime[1] = false;
    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 t = 0; t < num; t++)
    {
        for(int j = even[t]/2; j > 0; j--)
        {
            if(prime[j] && prime[even[t]-j])
            {
                cout << j << ' ' << even[t]-j << '\n';
                break;
            }
        }
    }
}

평가

에라토스테네스의 체를 활용한 문제이다. N/2 - i 와 N/2 + i의 합은 언제나 N이 된다는것을 활용하여 풀이가 가능하다.

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

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

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용의 명제이다. 임의의 숫자 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하는 문제이다.

이 때, 입력은 0이 입력될 때 까지 받아온다.

풀이

입력 받은 N들중, 가장 큰 N 값을 활용하여 2N까지의 소수를 구하는 배열을 동적 할당한다.

    vector<int> cases;
    int max = 0;
    int count = 0;
    while (1) {
        int i;
        cin >> i;
        if (i == 0)
            break;
        if (i > max)
            max = i;
        cases.push_back(i);
    }
    bool *prime = new bool[2 * max + 1];

그 후에, 에라토스테네스의 체를 활용하여 prime 배열을 완성시켜준다.

코드

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

int main() {
    vector<int> cases;
    int max = 0;
    int count = 0;
    while (1) {
        int i;
        cin >> i;
        if (i == 0)
            break;
        if (i > max)
            max = i;
        cases.push_back(i);
    }
    bool *prime = new bool[2 * max + 1];
    fill_n(prime, 2 * max + 1, 1);
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i <= sqrt(2*max); i++)
        if(prime[i] == true)
            for(int j = i*2; j <= (2*max); j += i)
                prime[j] = false;

    for(int j = 0; j < cases.size(); j++)
    {
        for(int k = cases[j]+1; k <= 2*cases[j]; k++)
            if(prime[k] == true)
                count++;
        cout << count << '\n';
        count = 0;
    }
    return 0;
}

평가

에라토스테네스의 체 개념을 활용하면 풀 수 있는 문제이다.

단계별로 풀어보기 - 수학 2 문제는 소수에 관한 문제가 유독 많은 듯 하다.

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

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

문제

자연수 N과 M이 주어졌을 때, M과 N 사이에 존재하는 소수를 한 줄씩 출력하는 프로그램을 작성하는 문제이다.

풀이

2581번 문제에서 사용했던 에라토스테네스의 체를 사용하면 풀 수 있는 문제이다.

N과 M중 더 큰 값인 N까지 존재하는 모든 소수를 bool prime 배열에 인덱스를 활용하여 나타내고,

M보다 크고 N보다 작은 소수를 모두 출력해주면 된다.

코드

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

int main() {
    int min,max;
    bool *prime;
    cin >> min;
    cin >> max;
    prime = new bool[max+1];
    fill_n(prime, max+1, 1);
    prime[0] = false;
    prime[1] = false;

    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)
            cout << i << "\n";
   return 0;
}

평가

에라토스테네스의 체를 활용한다면 금방 풀 수 있는 문제이다.

에라토스테네스의 체가 무엇인지 궁금하다면 링크를 참고하자.

2020/02/12 - [Algorithm/Baekjoon BOJ] - [백준 / BOJ] - 2581번 소수 C++ 풀이