this.winter plan.(01).백준[1065, 1978, 2581, 10814] (C++)

🫠 백준 1065 (https://www.acmicpc.net/problem/1065)

 

1065번: 한수

🧐 Algorithm 
1. 먼저 등차수열이어야 하므로 자리수간의 공차가 같아야 하기에 a-b와 b-c의 값이 동일해야함.
2. 이를 위해 함수 hansu를 만들었고 이를 100의자리수에서 사용.
3. 100~999까지 기준일 때 등차수열조건을 만족시켜야 하므로 다음과 같이 함수를 사용한다.

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

bool hansu (int num){
    int a = num / 100;
    int b = (num - a*100) / 10;
    int c = num % 10;
    return a-b == b-c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int cnt = 0;
    int num;    cin >> num;

    if (num <= 99){
        cout << num;
    }
    else if (num >= 100 && num <= 999) {
        for (int i = 100; i <= num; i++) {
            cnt += hansu(i);
        }
        cout <<  cnt + 99;
    }
    else
        cout << 144;
}

 

 

 

🫠 백준 1978(https://www.acmicpc.net/problem/1978)

1978번: 소수 찾기

🧐 Algorithm _ 소수를 찾는 법
1. a % b == 2라는 식은 약수를 구하는 식이며 
2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고
3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.

#include <iostream>
using namespace std;

int main() {
   ios_base::sync_with_stdio(0);

    int num;    cin >> num;
    int count = 0;
    for (int i = 0; i < num; i++) {
        int cnt = 0;
        int x; cin >> x;
        for (int j = 1; j <= x; j++)
            if (x % j == 0)
                cnt++;
        if (cnt == 2)
            count++;
    }
    cout << count << endl;
    return 0;
}

 

 

 

🫠 백준 2581(https://www.acmicpc.net/problem/2581)

2581번: 소수

🧐 Algorithm _ 소수를 찾는 법
1. a % b == 2라는 식은 약수를 구하는 식이며 
2. 이 약수의 개수를 세는 cnt라는 변수를 이용해 x의 약수개수를 구하고
3. 소수의 특징 (약수의 개수가 1과 자기자신)을 이용해 약수 개수가 2인 자연수 값들을 세준다.

이를 이용해 값들의 전체 합을 구해주고 가장 최소값은 작은 순서대로 vector에 넣어줬으므로
당연히 vector의 첫번째 원소에 들어있는 값이 최소값이 된다.

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


int main() {
   ios_base::sync_with_stdio(0);

    int M, N;   cin >> M >> N;
    int sum = 0;

    vector<int> v;

    for (int i = M; i <= N; i++) {
        int cnt = 0;
        for (int j = 1; j <= i; j++)
            if (i % j == 0)
                cnt++;
        if (cnt == 2){
            v.push_back(i);
            sum += i;
        }
    }

    if (v.size() == 0)
        cout << -1 << endl;

    else {
        cout << sum << endl;
        cout << v[0] << endl;
    }
}

 

 

 

 

🫠 백준 10814(https://www.acmicpc.net/problem/10814)

10814번: 나이순 정렬

🧐 Algorithm 
STL 중 하나인 pair를 사용한다.
(map의 경우, 값이 겹치면 저장이 되지 않기에 pair를 사용해 주었다.)

또한 stable_sort라는 함수를 사용해 주었다.
그냥 sort를 진행해주면 이는 quick sort방식의 불완전한 정렬방식이다. (unstable sort 방식)
즉, 원소가 같다면 바뀔 수 있는 정렬 방식이다. 

따라서 stable_sort를 사용하는데, 이는 merge sort를 기반으로 된 내장함수이기에 사용하게 되었다.


다만, stable한 정렬방식이 unstable한 정렬 방식보다 cost가 높기에 특별히 stable 정렬을 반드시 사용해야 하는 상황에는 sort()가 아닌, stable_sort()를 사용해주면 된다.

단, 이 문제의 핵심은 endl을 사용하면 시간초과가 걸릴 가능성이 높아 "\n"을 사용해야 한다.

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

pair<int, string> p[100000];

bool compare (pair<int, string> p1, pair<int, string> p2) {
    return p1.first < p2.first;
}

int main() {
   ios_base::sync_with_stdio(0);
    cin.tie(0);

    int num;
    cin >> num;

    for (int i = 0; i < num; i++) {
        int num; string str;  cin >> num >> str;
        p[i] = { num, str };
    }

    stable_sort(p, p+num, compare);

    for (int i=0; i<num; i++) {
        cout << p[i].first << " " << p[i].second << "\n";
    }
}