solved.ac Grand Arena #2 · Arena #2 / 3솔(2144)

백준과 solved ac 사이트가 힘을 합쳐 경쟁적 프로그래밍 컨텐츠가 생겼다

문제가 한국어로 출제되고, 백준 스타일의 문제에 익숙하므로 쉬울 줄 알았으나 글쎄요,,,,,,,,,,,

 

총평 :
1. 나는 경쟁적 프로그래밍을 잘 못하며 잘 하기 위해 태그가리기와 업솔빙을 많이 해야 함
2. 문제가 난이도순으로 정렬되어 있지 않아 다소 까다롭지만 스코어보드를 보면서 하면 됨
3. 풀이에 대한 증명(수학적/논리적)도 연습이 필요할 것 같다. C번 풀면서 느낌
4. 어렵지만 Atcoder보다는 친숙하고 할만하며, 업솔빙도 더 열심히 하게 될 것 같다

 

https://solved.ac/en/arena/2/editorial

solved.ac

 

A번 : 그냥 for문 잘 돌리고 사칙연산 잘해서 출력 잘하면 된다

 

B번 : FizzBuzz 

처음 봤을 땐 3의배수 판정법과 5의배수 판정법을 이용해야 하는 문제인 줄 알았으나, 문자열의 길이가 8이하이므로 거기까진 필요없음.

연속된 3개의 숫자 다음의 숫자가 뭔지 알아내야 하는데, 연속된 세 개 숫자 중에 무조건 하나는 3의배수도 아니고 5의 배수도 아니다.

증명>> 연속된 세 숫자 중 단 하나만 3의배수이고, 다른건 3의배수+1 또는 3의배수+2인 숫자일 것이다
또한 연속된 세 숫자는 5의배수 또는 5의배수+1 또는 5의배수+2 또는 5의배수+3 또는 5의배수+4 이므로,
연속된 세 숫자가 주어지면 그 중 하나는 반드시 3의배수도 아니고 5의배수도 아님이 보장됨

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

ll toint(string s){
	reverse(s.begin(),s.end());
	ll ans = 0;
	ll asd = 1;
	for (char z:s)
	{
		ans+=(z-'0')*asd;
		asd*=10;
	}
	return ans;
}

int main(){
	fastio;
	string a,b,c;cin>>a>>b>>c;
	ll d = 0;
	if(a!="Fizz"&&a!="Buzz"&&a!="FizzBuzz"){
		d=toint(a)+3;
	}
	else if(b!="Fizz"&&b!="Buzz"&&b!="FizzBuzz"){
		d=toint(b)+2;
	}
	else if(c!="Fizz"&&c!="Buzz"&&c!="FizzBuzz"){
		d=toint(c)+1;
	}



	if(d%3!=0&&d%5!=0){
		cout<<d;
	}
	else{
		if(d%3==0){
			cout<<"Fizz";
		}
		if(d%5==0){
			cout<<"Buzz";
		}
	}



	return 0;
}

그러므로 연속된 세 숫자 중 Fizz도 아니고 Buzz도 아니고 FizzBuzz도 아닌 걸 골라서 그녀석을 int로 바꿔준 뒤 정답이 무엇인지 알아내 출력하면 된다

 

C번 : Double it (못 품)

내 접근 방법 : priority_queue (min heap)을 만들어놓고, 원소들 중 최댓값을 알고 있다면,
최솟값과 최댓값을 알고 있는 상태가 되고, 얼마든지 최솟값을 뽑아서 쓰면서 정렬된 상태를 유지할 수 있다.

최솟값을 한개씩 계속 뽑아내면서 거기에 2를 곱한 뒤 pq에 삽입하고, 최솟값*2가 최댓값보다 클 때마다 최댓값을 갱신해준다면 최솟값과 최댓값을 계속 알 수 있다

그러니 충분한 횟수만큼 최솟값을 꺼내서 *2해 삽입하는 걸 계속하다 보면 풀릴 줄 알았음.

 

생기는 문제점 -> 일정 횟수 이상 반복시 오버플로우
오버플로우를 피하기 위해 수 범위를 제한했더니 -> 틀렸습니다

//WA code WA code WA code WA code WA code WA code WA code WA code WA code 
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(){
	fastio;
	int N;cin>>N;
	priority_queue<ll,vector<ll>,greater<ll>> pq;
	ll maxi = 0;
	for (int i = 0; i < N; i++)
	{
		ll a;cin>>a;
		maxi=max(a,maxi);
		pq.push(a);
	}
	ll ans = maxi-pq.top();

	ll cnt = 0;
	while (cnt<1000000)
	{
		cnt++;
		ll minnow = pq.top();
		pq.pop();
		pq.push(minnow*2);
		if(minnow*2>maxi){
			maxi=minnow*2;
		}
		if(maxi>0x3f3f3f3f3f3f)break;
		ans = min(maxi-pq.top(),ans);
	}
	cout<<ans;
	return 0;
}
//WA code WA code WA code WA code WA code WA code WA code WA code WA code

충분히 고민한 것 같으니 아레나 종료 이후 바로 에디토리얼을 보았다

 

에디토리얼의 첫번째 방법과 내 발상은 똑같으나, 나는 루프를 언제 종료해야 하는지를 생각해내지 못했다.

pq의 최솟값이 '처음에 주어진 원소들 중 최댓값'과 같아지거나 커질 때 루프를 종료하면 된다고 하는데ㅡ 이 부분에 대해 완벽히 이해하지는 못했음. 에디토리얼에 의하면, 그 상황이 되면 모든 원소들에 대해 한번 이상 *2연산을 취해야 하는 상황이고 마지막에는 원래 나와야 하는 답 *2가 답이 되어버린다고 함

어려운 문제일수록 증명에 빠싹해야 한다고 생각하는데 나는 아직 갈길이 멀다

 

D번 : Sum=Product (못품)

 

세그트리 + 브루트포스를 이용한 N*N 시간복잡도 풀이 -> 당연히 안 됨(TLE)

투 포인터 풀이 (이게 정해일 것 같다) -> l과 r을 적절히 전진시켜야 하는데, 뭔가 부족한 느낌 -> WA

//WA code WA code WA code WA code WA code WA code WA code WA code WA code 
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(){
	fastio;

	//투 포인터
	//내가 1인경우 더하기 우세
	//다음이 1인경우 더하기 우세
	//내가 2고 다음이 2인 경우 동일

	//동일한 경우->r을 뒤로 보낸다
	//합이 더 큰 경우-> r을 뒤로 보낸다

	//곱이 더 큰 경우-> 더하기 우세를 취하거나,곱이 작아질때까지 l 전진
	
	int l=0,r=0;
	int N;cin>>N;
	int arr[N];
	for (int i = 0; i < N; i++)cin>>arr[i];
	ll nsum=arr[0];ll nmul=arr[0];
	ll ans = 0;
	while (l<N)
	{
		if(nsum==nmul)ans++;

		if(nsum>=nmul){
			if(r+1<N){//곱을크게할수있다면 크게하기
				r++;
				nsum+=arr[r];
				nmul*=arr[r];
			}
			else{//글렀음
				l++;
				r=l;
				nsum=arr[l];nmul=arr[l];
			}
		}
		else{
			if(nsum==1||(r+1<N&&arr[r+1]==1)){//더하기 우세
				r++;
				nsum+=arr[r];
				nmul*=arr[r];
			}
			else{
				l++;
				r=l;
				nsum=arr[l];nmul=arr[l];
			}
		}
	}
	cout<<ans;
	return 0;
}
//WA code WA code WA code WA code WA code WA code WA code WA code WA code

대충 위의 코드를 설명하자면

예외))
현재 숫자가 x라고 할 때, +1 또는 *1을 하면, 더하기의 증가폭이 곱하기의 증가폭보다 크다
현재 숫자가 1이라고 할 때, +x를 하면 더하기의 증가폭이 곱하기의 증가폭보다 크다

이러한 예외의 발견에서 출발함. 위의 경우를 제외하고는

구간의 더하기 값이 구간의 곱하기 값보다 크다면 -> 곱하기 값이 더하기 값보다 커질때까지 r을 전진시킨다
구간의 더하기 값이 구간의 곱하기 값보다 작다면 -> 곱하기 값이 더하기 값보다 작아질때까지 l을 전진시킨다

그렇지만 위의 예외 때문에 뭔가가 정상적으로 돌아가지 않는다. 그래서 뒤의 구간을 확인해 얼마나 더 더하기할 수 있는지 / 얼마나 더 곱하기할 수 있는지를 판단해야 한다고 생각하기는 했다

 

잘 하면 풀 수 있을 것 같아 태그를 까 보았다. 아...애드혹이라고 한다

그럼 투포인터 풀이는 아닌듯. 내일 에디토리얼을 보겠다

 

E,G,H번 : 스코어보드에 푼 사람이 별로 없길래 걸렀다

 

F번 : 럭키 세븐 (못품->태그까고 품)

태그를 까보니 알겠다. 태그까기 전까진 다이나믹 프로그래밍이라고 생각도 못했음

아래와 같은 아이디어가 필요하다.

1. 7의배수에 어떤 수를 곱하든 그 숫자는 7의 배수임
2. 7의배수에 적절히 숫자를 더해나가서, 더해나간 숫자가 7의배수가 된다면 그 총합도 7의 배수임
3. 7의배수가 아닌 경우는 6가지밖에 없음. 7의배수+1 7의배수+2 ... 7의배수+6. 그러므로 7칸짜리 배열로 모든 숫자배열에 저장할 수 있음

 

그리고 C++의 경우 getline으로 입력을 받고 cin ignore로 엔터키 입력을 무시해주어야 한다 입력이 약간 까다로우니 주의

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(){
	fastio;
	int T;cin>>T;
	while (T--)
	{
		int N;cin>>N;
		cin.ignore();

		int arr[7]={0,1,0,0,0,0,0};

		for (int i = 0; i < N; i++)
		{
			int tmp[7]={0,0,0,0,0,0,0};
			
			string s;getline(cin,s);
			if(s[0]=='+'){
				for (int j = 0; j < 7; j++)
				{
					if(arr[j])tmp[(j+(s[2]-'0'))%7]=1;
				}
			}
			else{
				for (int j = 0; j < 7; j++)
				{
					if(arr[j])tmp[(j*(s[2]-'0'))%7]=1;
				}
			}
			if(s[4]=='+'){
				for (int j = 0; j < 7; j++)
				{
					if(arr[j])tmp[(j+(s[6]-'0'))%7]=1;
				}
			}
			else{
				for (int j = 0; j < 7; j++)
				{
					if(arr[j])tmp[(j*(s[6]-'0'))%7]=1;
				}
			}
			for (int j = 0; j < 7; j++)
			{
				arr[j]=tmp[j];
			}
		}
		if(arr[0]==1)cout<<"LUCKY\n";
		else cout<<"UNLUCKY\n";
	}
	
	return 0;
}

골드5따리를 못풀다니 반성하자

 

I번 : 와일드카드 괄호 문자열

괄호를 처리하는 문제는 아주 흔하고 잘 알려져 있다 보통 스택이나 재귀함수를 이용해 풀이한다
근데 이 문제는 그럴 필요가 없다

그렇지만 이 문제의 경우 와일드카드 문자 ?, *의 존재로 인해 케이스 따지기가 다소 까다롭다
근데 난 생각보다 쉽게 풀렸다

아래와 같은 발견이 필요하다

1. *문자가 중간에 껴있을경우 웬만하면 가능하지만 안되는경우는?? -> )ㅁㅁㅁㅁ , ㅁㅁㅁㅁ( 이런식으로, 바깥을 바라보고 있는 괄호가 존재할 경우 불가능하다. 엄밀하게 따지면, 바깥을 보고 있는 괄호의 개수가 안쪽을 보고 있는 괄호와 ?의 개수를 합친 것보다 많을 때 불가능하다.

2. *문자가 존재하지 않을 경우, 전체 문자의 개수가 홀수라면 절대 괄호가 짝을 이룰 수 없음

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;

int main(){
	fastio;
	int T;cin>>T;
	while (T--)
	{
		string s;cin>>s;
		//앞에서부터 검사
		int l=0,r=0,q=0,w=0;
		int flg = 0;//NO인가아닌가
		for (auto i:s)
		{
			if(i=='('){l++;}
			if(i==')'){r++;if(r>l+q&&w==0)flg=1;}
			if(i=='?'){q++;}
			if(i=='*'){w++;}
		}
		if(flg){cout<<"NO\n";continue;}
		l=0;r=0;q=0;w=0;
		reverse(s.begin(),s.end());
		//뒤에서부터 검사
		for (auto i:s)
		{
			if(i==')'){l++;}
			if(i=='('){r++;if(r>l+q&&w==0)flg=1;}
			if(i=='?'){q++;}
			if(i=='*'){w++;}
		}
		if(flg){cout<<"NO\n";continue;}
		if(w==0&&s.length()%2==1){cout<<"NO\n";continue;}
		cout<<"YES\n";
	}
	
	return 0;
}

바깥쪽을 바라보고 있는 괄호만 잘 찾아주면 된다. 이를 편하게 하기 위해 앞에서부터 검사 한번 하고 뒤에서부터 검사 한번 삭 돌리면 됨