[C++] 15721 - 번데기 (실버5)

1. 문제 설명

 

15721번: 번데기

---

2. 아이디어

 

심심해서 구글링 하면서 놀다가 우연히 발견한 문제였는데

문제 유형은 브루트 포스라고 되어 있고 실제로 그렇게 해도 상관 없지만,

수학적으로 최적화가 가능할 것 같아서 풀어봤다. (꽂히면 해봐야 하는 타입)

근데 문제가 워낙 간단해서 별다른 성과를 얻지는 못했다.

 

잘 생각해보면 이 문제는 T번 째 0 혹은 1의 위치만 알면 인원수의 나머지를 구하면 답이 나온다.

result = T_index % A

그럼 이 문제는 "T번 째 0 혹은 1의 인덱스를 구하는 방법"을 묻는 문제로 바뀐다.

그런데 패턴이 너무 적나라하지 않은가.

 

몇 번째 회차던 간에 처음 4번은 '0 - 1 - 0 - 1'이 반복된다.

그 다음은 N(몇 번째 돌고 있는가?)만 안다면 0과 1의 개수는 2+N개로 위치를 금방 구할 수 있다. 

 

그럼 "A가 몇 번째 회차에 해당하는가"를 구해야 하는데, 조금만 생각해보면 금방 구할 수 있다.

대충 설명하고 치우려다가 글로 설명하기 너무 힘들어서 포기

빨간색은 Index 값이고, 주황색은 0("번"), 보라색이 1("데기") 번호라고 치고 숫자를 잘 지켜보면 답이 나온다.

Index는 4 + 2*N만큼 증가한다.

각 N에서 존재할 수 있는 최대 "번", "데기"의 최대 번호는 이전 값의 (4 + N)을 더한 값이다.

이걸 이용해서 조건식을 잘 걸어주면 N이 나올 것이고, 인덱스 구해서 인원수로 나머지 구한 다음 출력시키면 끝난다.

 

물론 처음에도 말했 듯이 무식하게 긁으면서 해도 상관 없는 문제고,

제출하고 다른 블로그 좀 훑어봤더니 다들 그렇게 풀고 계시더라.

---

3. 코드

#include <iostream>

#define endl "\n"

using namespace std;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, t, flag; cin >> a >> t >> flag;
    int round=1, total=7;
    int tmp = 4;
    int now;

    while (t > tmp) {
        tmp += 4 + round++;
        total += 4 + 2*(round+1);
    }
    tmp -= (4 + round-1);
    total -= (4 + 2*(round+1));

    if (t - tmp <= 2)
        now = (!flag) ? total + 2*(t-tmp)-1 : total + 2*(t-tmp);
    else
        now = (!flag) ? total + 4 + (t-tmp-2) : total + 4 + (round+1) + (t-tmp-2);

    cout << now % a << endl;

    return 0;
}