공부흔적

문제 링크

풀이 )

  배열에 있는 수를 앞 또는 뒤에서 뺄 수 있도록 하기 위해 deque에 넣었다.

  처음 방향 dir을 true로 설정하고, 함수 R가 올 때마다 dir을 바꿔준다.

  dir에 따라 함수 D가 올 때 true인 경우 앞에서 빼주고 (pop_front()), false인 경우 뒤에서 빼준다. (pop_back())

  이 때, 현재 deque가 비어있는데 D가 나오는 경우 error를 출력하면서 다음 케이스를 실행한다.

  함수를 수행한 결과 deque가 비어있는 경우 "[]"만 출력하고 다음 케이스를 실행하고,

  비어있지 않은 경우 dir에 따라 앞, 뒤에서부터 출력한다.

#include <iostream>
#include <string>
#include <deque>

using namespace std;

int main(void){
    int t;
    cin >> t;
    while(t--){
        string func, s;
        int n;
        cin >> func;
        cin >> n;
        cin >> s;

        deque<int> dq;
        int len = s.length();
        int tmp = 0;
        for(int i = 1; i < len; ++i){
            if(s[1] == ']')
                break;
            if(s[i] == ',' || s[i] == ']'){
                dq.push_back(tmp);
                tmp = 0;
            }
            else
                tmp = tmp*10+s[i]-'0';
        }

        bool dir = true;
        int func_len = func.length();
        bool flag = 0;
        for(int i = 0; i < func_len; ++i){
            if(func[i] == 'R')
                dir = !dir;
            else{
                n--;
                if(dq.empty()){
                    cout << "error" << endl;
                    flag = true;
                    break;
                }
                if(dir)
                    dq.pop_front();
                else
                    dq.pop_back();
            }
        }
        if(flag)
            continue;

        if(n == 0){
            cout << "[]" << endl;
            continue;
        }
        if(dir){
            for(int i = 0; i < n; ++i){
                if(i == 0)
                    cout << '[';
                cout << dq.front();
                dq.pop_front();
                if(i == n-1)
                    cout << ']' << endl;
                else
                    cout << ',';
            }
        }
        else{
            for(int i = 0; i < n; ++i){
                if(i == 0)
                    cout << '[';
                cout << dq.back();
                dq.pop_back();
                if(i == n-1)
                    cout << ']' << endl;
                else
                    cout << ',';
            }
        }
    }
}

주의 )

  각 경우에 대해서 조건을 간단하게 나타낼 수 있다.  ex ) 5를 지나가는 경우 cur+prev == 10

  이 때 4를 지나가는 경우 cur+prev == 8로 나타내는 경우 (2, 6)과 같은 예외가 있기 때문에 주의해야한다.

문제 링크

풀이 )

  규칙성을 찾아내는 문제다.

  풀어야 할 고리의 개수에 주목을 해보면

  1번 끊었을 때 가능한 무게는 7g까지이다. 2 1 4

  2번 끊었을 때는 1이 2개가 있으므로 3이 필요하고, 앞의 3개의 조합(1 1 3)으로 5까지 만들 수 있으므로 6이 필요하고

  3 1 6 1 의 조합으로 11까지 만들 수 있으므로 마지막으로 12까지 총 23(3 1 6 1 12)까지 표현이 가능하다.

  같은 방식으로 3번 끊었을 때는 총 4 1 8 1 16 1 32 의 조합으로 63까지 표현이 가능하다.

  최대로 나타낼 수 있는 무게를 좀더 보기 쉽게 나타내면

•   1번 - 2 1 4 -> 7
•   2번 - 3 1 6 1 12 -> 23
•   3번 - 4 1 8 1 16 1 32 -> 63
•   4번 - 5 1 10 1 20 1 40 1 80 -> 159
•   n번 - (n+1) 1 (n+1)*2 1 (n+1)*2² 1 ... 1 (n+1)*2ⁿ 의 꼴임을 알 수 있다.

  식을 정리하면 (n+1)(1+2+2²+...+2ⁿ)+1*n = (n+1)(1+2+2²+...+2ⁿ)+(n+1)-1 = (n+1)2ⁿ⁺¹-1이다.

  bound를 (n+1)2ⁿ⁺¹라고 할 때 n값을 늘려주다가 입력값을 초과하는 경우 멈춰주면 된다.

  다음 bound를 구할 때는 이전의 n으로 나눠준 후 다음번인 n+1을 곱하고 2를 한번 더 곱해서 구했다.

#include <cstdio>
using namespace std;

int main(void)
{
  long long n, bound = 8, ans = 1;
  scanf("%lld", &n);
  while(n >= bound){
    ans++;
    bound = bound / ans * (ans+1) * 2;
  }
  printf("%lld\n", ans);
}