이 문제는 사실 브론즈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, strlen 등 string.h에 포함되어있는 여러 함수들을 사용할 수 있게된다.
다른것보다 문제를 이해하는데에 시간이 오래걸렸다. 문제만 이해한다면 그냥 시키는 대로만 하면 풀 수 있다.
#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;
}
괄호를 적절히 넣는다는 말은 그냥 계산 우선순위를 만들라는 것이고 가장 작은 수를 만들기 위해서는 숫자와 -사이에 괄호가 있다면 수가 -가 되어서 가장 작은 수가 될 것이다.
이 예제를 보면 결국
$$ 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;
}
간단히 풀려면 정말 간단하다. 그냥 입력받은 수 배열에 넣고 그 이후 숫자 입력 받을때마다 반복문으로 체크해보면 된다.
#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;
}
중간에 배열이 포인터 동적할당으로 바꼈는데 혹시나 배열 크기문제 때문인가 싶어서 수정했었는데 아니였다. 그래도 그냥 메모리 크기 생각해서 놔뒀다.
