BOJ 26151 - NATO 음성 기호와 쿼리

https://www.acmicpc.net/problem/26151

26151번: NATO 음성 기호와 쿼리

 

진짜 오랜만에 푸는 백준 문제.

입사하고 난 다음 알고리즘 쪽 머리가 너무 굳은 것 같아 부담없이 하나 풀어보기로 하였다.

알고리즘 자체는 그렇게 어려운 편이 아니지만 자질구리하게 처리해야 하는게 귀찮았다.

더불어서 거의 처음으로 Visual Studio를 쓰다가 vim에서 하다보니 디버그가 익숙하지 않아 더 귀찮아졌다.

이정도면 그렇게 시간을 투자 안해도 될 문제 같은데 1시간 반...이나 써버렸다.

 

문제풀이는 아마 한양대학교 프로그래밍 경시대회 해설에 나와있을 거니깐 여기서는 설명을 자세하게 하지는 않겠다

그냥 골드 3~4정도의 아이디어 3개가 뭉쳐서 플레3이 되어버린 느낌. 그 아이디어 3개란,

(1) x가 30 이상이면 확정적으로 한 문자가 확장되는 게 10^18의 개수를 넘어감(4^30 > 10^18) - 고려하지 않아도 됨

(2) dp로 x가 0~30일때 확장되는 개수를 구함.

(3) 처음에 S가 200000이기 때문에 처음 진입하는 경우에는 이진탐색을 넣어줘야 함

#include <stdio.h>
#include <string.h>
#define LIMIT 1000000000000000000LL
typedef long long ll;
char* s[27]={"ALFA","BRAVO","CHARLIE","DELTA","ECHO","FOXTROT","GOLF","HOTEL","INDIA","JULIETT","KILO","LIMA","MIKE","NOVEMBER","OSCAR","PAPA","QUEBEC","ROMEO","SIERRA","TANGO","UNIFORM","VICTOR","WHISKEY","XRAY","YANKEE","ZULU"};

int Q;

ll dp[26][31];
int hahalen;
ll gogogo[200003];
char whatAtThis(char* now, ll x, ll p, bool start=false){
	if (start){
		int st=0, en=hahalen;
		while(st<en-1){
			int md=(st+en)/2;
			if (gogogo[md]>p){
				en=md;
			}
			else{
				st=md;
			}
		}
		return whatAtThis(s[now[st]-'A'], x-1, p-gogogo[st]);
	}
	else{
		int len=strlen(now);
		for (int i=0;i<len;i++){
			char go=now[i];
			if (p==0){
				return go;
			}
			if (p<dp[go-'A'][x]){
				return whatAtThis(s[go-'A'], x-1, p);
			}
			else{
				p-=dp[go-'A'][x];
			}
		}
	}
}

char haha[200003];
int main()
{	
	for (int i=0;i<=30;i++){
		for (int j=0;j<=25;j++){
			if (i==0) dp[j][i]=1;
			else{
				int len=strlen(s[j]);
				for (int go=0;go<len;go++){
					char k=s[j][go];
					dp[j][i] += dp[k-'A'][i-1];
				}
				if (dp[j][i]>=LIMIT+1) dp[j][i]=LIMIT+1;
			}
		}
	}
	scanf("%s %d",haha,&Q);
	
	hahalen = strlen(haha);
	ll x=0;
	for (int i=0;i<hahalen;i++){
		gogogo[i+1]=gogogo[i]+1;
	}
	while(Q--){
		int cmd;
		ll xp;
		scanf("%d %lld",&cmd,&xp);
		if (cmd==1){
			ll px=x;
			x+=xp;
			if (x>30) x=30;
			if (px!=x){
				for (int i=0;i<hahalen;i++){
					gogogo[i+1]=gogogo[i]+dp[haha[i]-'A'][x];
					if (gogogo[i+1]>=LIMIT+1) gogogo[i+1]=LIMIT+1;
				}
			}
		}
		else{
			printf("%c",whatAtThis(haha,x,xp-1,true));
		}
	}
	return 0;
}