C++ 공부 6일차 (1181, 2164, 11650)

오늘 공부한 백준

1181, 2164, 11650

 

 

2164

큐를 모르는 상태에서 풀다보니 규칙을 발견해 그것을 수식으로 옮겼다.

입력 값이 3인 상태에서부터 보자.

입력    출력

입력	출력
3	2
4	4
5	2
6	4
7	6
8	8
9	2
10	4
11	6
12	8

눈에 띄에 출력값이 짝수이다

입력값이 4일때, 8일때, 16일때 끊어보면

입력값이 3,4 / 5,6,7,8 / 9,10,11,12,13,14,15,16 /

출력값이 2,4 / 2,4,6,8 / 2, 4,  6,  8,10,12,14,16 / 인 것을 알 수 있다.

입력값의 범위는 다음 수식으로 표현 할 수 있다.

결국 입력값이 N이라고 할 때 그 출력값을 A라고 했을 때 N이 해당 범위에 들어가면 그 범위의 최대값에서의 차 * 2를 최대값에서 뺴면 출력값이 나오는 것을 알 수 있다.

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


int main() {

    int n;
    cin >> n;

    int i = 1;
    int ans;

    if(n == 1 || n == 2){
        cout << n << "\n";
        return 0;
    }
    while(1) {
        if(pow(2,i) + 1 <= n && n <= pow(2,i+1)){
            ans = i;
            break;
        }
        else i++;
    }

    cout << pow(2,ans + 1) - pow(2,i + 2) + 2*n << "\n";
}

 

큐를 이용한 다른 풀이

#include <queue> 

int n;
cin >> n;
queue<int> q;
for(int i = 0; i < n; i++) {
    q.push(i)
}

for(int i = 0; i < n; i++) {
    while(q.size() != 1) {
        q.pop();
        q.push(q.top());
        q.pop();
    }
}

cout << q.front() << "\n";

queue <데이터 타입> 이름 ; 으로 queue을 선언한다.

물론 밖에 #include <queue>를 추가해준다

 

---

11650 좌표 정렬하기

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

typedef struct{
    int first;
    int second;
} co;

bool compare(const co &a, const co &b) {
    if(a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
}
int main() {
    int n;
    cin >> n;

    co coordinate[100000];
    for(int i = 0; i < n; i++) {
        cin >> coordinate[i].first >> coordinate[i].second;
    }

    sort(coordinate, coordinate + n, compare);

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