1. 기본 풀이


이 문제는 사실 브론즈2 밖에 안되는 굉장히 쉬운 문제다. 당장 재귀 코드도 다주기 때문에 그대로 풀면 된다.

 #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;

int cnt;

int recursion(const string s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const string s){
    return recursion(s, 0, s.size()-1);
}

int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

그러나 이대로 풀면 바로 TLE가 나온다. 그렇다면 어떻게 풀어야 될까?

 

2. 맞왜틀?


이는 c++의 string 타입의 특성에 의한 것이다.

string은 문자열을 함수 인자로 넘겨줄 때 문자열을 통째로 넘겨주기 때문에 시간이 오래걸리지만, char *는 문자열을 넘겨줄 때 시작주소만을 넘겨주기 때문에 string보다 더 빠르다.

이를 해결하는 방법은 총 2가지가 있다.

1. char *사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;

int cnt;

int recursion(const char* s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char* s){
    return recursion(s, 0, strlen(s)-1);
}

int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        char s[1001];
        cin >> s;
        cout << isPalindrome(s) << ' ' << cnt << endl;
    }
    return 0;
}

이렇게 string대신 char *로 풀면 된다.

 

2. s.c_str()사용

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;

int cnt;

int recursion(const char* s, int l, int r){
    cnt++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char* s){
    return recursion(s, 0, strlen(s)-1);
}

int main(){
    fastio;
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cnt = 0;
        string s;
        cin >> s;
        cout << isPalindrome(s.c_str()) << ' ' << cnt << endl;
    }
    return 0;
}

 사실상 이 포스트를 작성한 실질적인 이유인데, std::string c_str()함수를 사용하면 string형이 char *형으로 변환된다. 이를 활용하면 기존에 string타입에서는 사용할 수 없었던 strtok, strlenstring.h에 포함되어있는 여러 함수들을 사용할 수 있게된다.

 

 이는 잘 사용한다면 큰 도움이 될 것 같다.

'PS' 카테고리의 다른 글

[BOJ] 1094 막대기  (0) 2023.02.12
[BOJ] 1013 Contact  (0) 2023.02.09
[BOJ] 1541 잃어버린 괄호  (0) 2023.01.29
[BOJ] 4949 균형잡힌 세상  (0) 2023.01.17
[BOJ] 1920 수 찾기  (0) 2023.01.16

1. 기본 풀이


다른것보다 문제를 이해하는데에 시간이 오래걸렸다. 문제만 이해한다면 그냥 시키는 대로만 하면 풀 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int n, num = 64;
    vector<int> v;
    cin >> n;
    v.push_back(64);

    while(num > n) {
        int min = v[0];
        int min_idx = 0;
        for(int i = 0; i < v.size(); i++) {
            if(min > v[i]) {
                min = v[i];
                min_idx = i;
            }
        }
        v.erase(v.begin() + min_idx);
        v.push_back(min / 2);
        num -= min / 2;
        if(num < n) {
            v.push_back(min / 2);
            num += min / 2;
        }
    }

    if(num == n) cout << v.size() << endl;
    else cout << -1 << endl;

    return 0;
}


이해하지 못한 이유

이해를 못한 부분은 1-2.
위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.
이 부분인데 처음 64에서 절반 중 하나를 버리고 나머지 하나를 버리면 0인데 뭐 어쩌라는 거지라는 생각을 계속 했다. 이 부분 때문에 구글링도 했는데 나랑 비슷한 사람이 은근 있더라...
어쨌든 저 부분을 풀어서 설명하자면
위에서 자른 절반의 막대와 그 외의 나머지 막대의 길이의 합이 X보다 작으면 절반의 막대 두 개를 그대로 챙기고, 크거나 같다면 둘 중 하나를 버린다는 뜻이다.
즉, 막대의 길이의 합이 X보다 작다면 자르기만 하고 둘 다 챙긴다는 뜻이다.




2. 또 다른 풀이


문제를 풀고난 이후 태그를 봤는데 비트마스킹을 봤다. 그래서 왜 이 문제가 비트마스킹인가? 에 대해서 생각해봤다.
이 문제는 기본 막대기의 크기가 (64) ((1000000 == 2^6))으로 주어져있다.
그리고 항상 2씩 나누면서 버릴지 유지할지를 결정한다.

예를 들어보자. 백준에 기본적으로 제시되어 있는 예시인 23을 해보자.

64를 2로 나누면 32. 32는 23보다 크니 버림.

32를 2로 나누면 16. 16은 23보다 작으니 유지

16을 2로 나누면 8. 16 + 8은 23보다 크니 버림.

8을 2로 나누면 4. 16 + 4는 23보다 작으니 유지.

4를 2로 나누면 2. 16 + 4 + 2는 23보다 작으니 유지.

2를 2로 나누면 1. 16 + 4 + 2 + 1은 23과 같다.

결론적으로 23 = 16 + 4 + 2 + 1. 어딘가 익숙한 숫자다.


즉, 항상 2로 나누기 때문에 결과값은 입력값의 비트 개수다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int x;
    cin >> x;
    cout << bitset<7>(x).count() << endl;
    return 0;
}




여담으로 이 포스팅은 처음으로 마크다운으로 작성되었다.

'PS' 카테고리의 다른 글

[BOJ] 25501 재귀의 귀재  (0) 2023.02.13
[BOJ] 1013 Contact  (0) 2023.02.09
[BOJ] 1541 잃어버린 괄호  (0) 2023.01.29
[BOJ] 4949 균형잡힌 세상  (0) 2023.01.17
[BOJ] 1920 수 찾기  (0) 2023.01.16

결국 

$$ (100+1+ | -1)+ $$

이 식을 만족하는지 안하는지를 체크하면 된다는 것이다.

 

 처음에 오토마타 전공수업때 배웠던 state machine이 생각났었으나 그렇게 코딩할 생각은 못하고... 조건을 생각해서 전부 노가다로 풀려고 했었다. 그러나 아무리 해도 뭔가 조건이 너무 복잡하고 나오는 경우의 수도 많아서 풀기가 힘들었다.

 

 그래서 가장 처음에 생각했던 state machine을 이용한 풀이를 생각해봤다.

내가 직접그린 NFA다(발그림..)

 

우선 initial state는 S0이며, 위 그림과 같이 상태가 변화한다.

이를 코드로 작성하면,

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

void solve() {
    int state[8][2] = {
        {1, 2},     //s0
        {-1, 0},    //s1
        {3, -1},    //s2
        {4, -1},    //s3
        {4, 5},     //s4
        {1, 6},     //s5
        {7, 6},     //s6
        {4, 0}      //s7
    };
    int current = 0;
    string s;
    cin >> s;

    for(int i = 0; i < s.size(); i++) {
        if(current == -1) break;
        current = state[current][s[i] - '0'];
    }

    if(current == 0 || current == 5 || current == 6) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    fastio;
    int T;
    cin >> T;
    for(int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

 이러한 정말 깔끔한 코드가 나오는데 나는 왜 이걸 조건 하나하나 다 찾아가며 했는지 현타가 오더라...

 

 그리고 이 포스트를 작성하면서 생각난건데 오토마타의 형식언어를 통해 정규식을 만들 수 있는데 이게 그 정규식이 아닌가? 라는 생각이 들었다. 그런 생각이 들고나서 파이썬에는 정규식을 확인할 수 있는 메소드가 있는걸로 아는데 C++에도 있는지 찾아보았다.

 

https://modoocode.com/303

 

씹어먹는 C++ - <17 - 2. C++ 정규 표현식(<regex>) 라이브러리 소개>

 

modoocode.com

있더라... 현타가 좀 많이 왔다.

 

이를 활용해 코드를 작성해봤다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using ull = unsigned long long;
using u = unsigned;
using pii = pair<int, int>;

int main() {
    fastio;
    int T;
    cin >> T;
    regex re("(100+1+|01)+");

    for(int i = 0; i < T; i++) {
        string s;
        cin >> s;
        cout << (regex_match(s, re) ? "YES" : "NO") << endl;
    }

    return 0;
}

 

하... 분명 풀었는데 현타가 정말 많이오는 문제였다.

'PS' 카테고리의 다른 글

[BOJ] 25501 재귀의 귀재  (0) 2023.02.13
[BOJ] 1094 막대기  (0) 2023.02.12
[BOJ] 1541 잃어버린 괄호  (0) 2023.01.29
[BOJ] 4949 균형잡힌 세상  (0) 2023.01.17
[BOJ] 1920 수 찾기  (0) 2023.01.16

 

 +와 -만을 이용한 식을 입력받아 괄호를 적절히 넣어 가장 작은 수를 만드는 문제다.

 

 괄호를 적절히 넣는다는 말은 그냥 계산 우선순위를 만들라는 것이고 가장 작은 수를 만들기 위해서는 숫자와 -사이에 괄호가 있다면 수가 -가 되어서 가장 작은 수가 될 것이다.

 

이 예제를 보면 결국

$$ 55-(50+40) $$

이러한 식이 되어 결과값이 35가 나오게 된다.

 

 이는 이후 +가 나오면 위 식과 같이 한번에 -를 하게되고 만약 -가 나온다면 한 번 괄호를 닫았다가 다시 괄호를 열게된다. 즉, 이후 어떠한 연산자가 나오든지 상관없이 쭉 -연산만 진행해주면 된다. 따라서 minus에 관한 bool타입 변수를 만들어서 이를 확인하면 될 것 같다.

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;


int main() {
    int res = 0;
    string str, num;
    bool minus = false;
    cin >> str;


    for(int i = 0; i <= str.length(); i++) {
        if(str[i] == '-' || str[i] == '+' || i == str.length()) {
            if(minus) res -= stoi(num);
            else res += stoi(num);
            num = "";
        } else {
            num += str[i];
        }

        if(str[i] == '-') minus = true;
    }
    cout << res << endl;
    return 0;
}

'PS' 카테고리의 다른 글

[BOJ] 25501 재귀의 귀재  (0) 2023.02.13
[BOJ] 1094 막대기  (0) 2023.02.12
[BOJ] 1013 Contact  (0) 2023.02.09
[BOJ] 4949 균형잡힌 세상  (0) 2023.01.17
[BOJ] 1920 수 찾기  (0) 2023.01.16

이 문제는 사실 군대에서 한 번 풀었었던 문제다. 스택에 여는 괄호는 무조건 push, 닫는 괄호가 나올 때 top과 짝이 맞으면 넘어가고 짝이 맞지 않거나 스택이 비었으면 no를 출력하는 간단한 문제다.

 

 다만 군대에서 풀었을 때 TLE가 발생했는데 그 이유는 초기화의 문제였다. 이 문제는 C++로 풀었는데, 만약 C로 풀었다면 그냥 top = -1을 대입하면 빠르게 초기화할 수 있었겠지만 stl을 사용하다보니 초기화 방법이 다음과 같이 할 수밖에 없었다.

void init() {
  if(s.empty()) return;
  while(!s.empty()) s.pop();
}

그런데 정말 간단한 방법을 찾았다.

 

"."이 입력될 때까지 무한루프고, 어차피 한 줄씩 입력받으면서 바로 결과값을 출력한다면 그냥 매 루프마다 스택을 새로 선언하면 되지 않을까?

 

#include <iostream>
#include <string>
#include <stack>

using namespace std;

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


    while(1) {
        string temp;
        getline(cin, temp);
        if(temp.length() && temp[0] == '.') break;

        stack<char> s;
        bool res = true;
       
        for(int i = 0; i < temp.length(); i++) {
            if(temp[i] == '(' || temp[i] == '[')
                s.push(temp[i]);
            else if(temp[i] == ')') {
                if(!s.empty() && s.top() == '(') s.pop();
                else {
                    res = false;
                    break;    
                }
            } else if(temp[i] == ']') {
                if(!s.empty() && s.top() == '[') s.pop();
                else {
                    res = false;
                    break;    
                }
            }
        }
        if(res && s.empty()) cout << "yes\n";
        else cout << "no\n";
    } 

    return 0;
}

그 결과는 성공이였다.

 

'PS' 카테고리의 다른 글

[BOJ] 25501 재귀의 귀재  (0) 2023.02.13
[BOJ] 1094 막대기  (0) 2023.02.12
[BOJ] 1013 Contact  (0) 2023.02.09
[BOJ] 1541 잃어버린 괄호  (0) 2023.01.29
[BOJ] 1920 수 찾기  (0) 2023.01.16

간단히 풀려면 정말 간단하다. 그냥 입력받은 수 배열에 넣고 그 이후 숫자 입력 받을때마다 반복문으로 체크해보면 된다.

#include <stdio.h>
#define MAX_SIZE 100000

int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];

    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        t = 0;
        scanf("%d", &temp);
        for(int j = 0; j < n; j++) {
            if(arr[j] == temp) {
                printf("1\n");
                t = 1;
                break;
            }
        }
        if(t == 0) printf("0\n");
    }

    return 0;
}

그리고 이렇게 대충 반복문으로 코드를 짜면 정말 당연하게도

빨간색 시간초과를 볼 수 있다.

 

그렇다면 이 문제는 탐색알고리즘을 써야 된다는 건데 그 중 제일 간단하다고 생각하는 이진탐색을 사용했다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000

int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target);

int main() {
    int n, m;
    int t, temp;
    int arr[MAX_SIZE];

    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    qsort(arr, n, sizeof(int), compare);
    
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp) != -1) printf("1\n");
        else printf("0\n");
    }

    return 0;
}

int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    if(*(int *)a < *(int *)b) return -1;
    if(*(int *)a == *(int *)b) return 0;
}

int bst(int* arr, int start, int end, int target) {
    if(start > end) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target);
    else return mid;
}

 이렇게 예쁜 이진탐색코드를 작성했더니 틀렸다고 나온다. 이때부터 맞왜틀을 계속 외치기 시작한다. 분명 예제도 정상적으로 작동하고 다른거 이상한거 넣어도 정상적으로 작동하는데 왜 안되지?

 

그때부터 눈이 돌아가서 하나씩 바꿔보기 시작하다가 어쩌다 반례를 찾았다.

원래라면 결과값이 0이 나와야 하지만 1이 나와버렸다. 반례를 찾았으니 이것을 해결하기 위해 열심히 디버거를 돌려봤는데, 

 

배열에서 우리가 입력을 하고 사용하는 크기는 1이다. 즉, 인덱스는 0까지만 사용한다. 그러나 두번째 bst함수를 들어갔을 때 start와 end가 1이 되고 이에 따라 mid값도 1이 된다. 여기서 arr[1]을 불러왔을 때 이 값이 0이 나오고 그게 target과 같은 수라서 최종 결과로 1이 출력되는 것이다.

 

 이 결과가 결국엔 사용가능한 index를 넘어가서 이러한 결과가 나온다고 생각해서 bst함수에 함수의 크기 len이라는 인자를 추가해주고 처음 탈출 조건에 start > len이라는 조건을 추가해줬다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100000

int compare(const void *a, const void *b);
int bst(int* arr, int start, int end, int target, int len);

int main() {
    int n, m;
    int t, temp;
    int* arr;

    scanf("%d", &n);
    arr = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    qsort(arr, n, sizeof(int), compare);

    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &temp);
        if(bst(arr, 0, n, temp, n) != -1) printf("1\n");
        else printf("0\n");
    }

    return 0;
}

int compare(const void *a, const void *b) {
    if(*(int *)a > *(int *)b) return 1;
    else if(*(int *)a < *(int *)b) return -1;
    else return 0;
}

int bst(int* arr, int start, int end, int target, int len) {
    if(start > end || start >= len) return -1;
    int mid = (start + end) / 2;
    if(arr[mid] > target) return bst(arr, start, mid - 1, target, len);
    else if(arr[mid] < target) return bst(arr, mid + 1, end, target, len);
    else return mid;
}

 중간에 배열이 포인터 동적할당으로 바꼈는데 혹시나 배열 크기문제 때문인가 싶어서 수정했었는데 아니였다. 그래도 그냥 메모리 크기 생각해서 놔뒀다.

 

 

'PS' 카테고리의 다른 글

[BOJ] 25501 재귀의 귀재  (0) 2023.02.13
[BOJ] 1094 막대기  (0) 2023.02.12
[BOJ] 1013 Contact  (0) 2023.02.09
[BOJ] 1541 잃어버린 괄호  (0) 2023.01.29
[BOJ] 4949 균형잡힌 세상  (0) 2023.01.17

+ Recent posts