1. 문제 설명
15721번: 번데기
예를 들어 7명이 있고, 16번째 등장하는 “뻔”을 부른 사람의 번호를 알고 싶다면 입력은 7 16 0이다. 4명이 있고 6번째 등장하는 “데기”를 부른 사람의 번호를 알고 싶다면 입력은 4 6 1이며, 이
www.acmicpc.net
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;
}