[도전 7일차] Codejam 2019 예선 (1)

Codejam 2019 Qualification Round

문제 1: Foregone Solution

 

문제 링크

 

사용 알고리즘 :

 

문제 설명: 

4가 포함된 자연수 N (ex) 14)을  4가 포함되지 않은 두 자연수 A,B로 쪼개는 문제다.

N은 T번 주어진다.

풀이:

대회 당시 Visible Testcase는  N < 10^9 였고 Hidden Testcase 는 N<10^100 이였다.

 

먼저 N<10^9 부터 접근해보자.

테스트케이스가 100개이므로 당연히 1~N까지 살펴보는 것은 TLE다.

그런데 곰곰히 생각해보면 아무렇게나 수를 분할하면 되므로 각 자리에 맞추어 수가 7~9가 아닌 경우에는 절반으로 쪼개고 7~9면 1과 나머지로 나누자. 

ex) 145 --> 123 : 022

생각해보니 앞에 0이 오는 경우를 처리 안했는데, AC 받았다.

 

여담으로 나는 AC 받는데 20분 이상 걸렸는데, 실전에서는 생각을 다 끝내고 10분 내로 짜는게 중요하다.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,t;
void solve(){
	string s,a,b;
	s.clear(); a.clear(); b.clear();
	cin>>s;
	for(char x : s){
		int t=x-'0';
		if(t>=7&&t<=9)
			a.push_back(t-1+'0'),b.push_back(1+'0');
		else
			a.push_back((t+1)/2+'0'),b.push_back(t/2+'0');
		
	}
	cout<<a<<' '<<b<<'\n';
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>t;
	for(int i=1;i<=t;i++){
		cout<<"Case #"<<i<<": ";
		solve();
	}
}