[BOJ 14453] Hoof, Paper, Scissors (Silver)

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

14453번: Hoof, Paper, Scissors (Silver)

 

- 문제 요약

 

소들은 "가위바위보"의 소 버전인 "발굽, 종이, 가위" 게임을 즐겨합니다.

 

"발굽, 종이, 가위" 게임을 할 때는 두 마리의 소가 서로 맞붙어 놉니다.

셋을 세고 동시에 발굽, 종이 조각 또는 가위를 냅니다.

발굽은 가위를 이기고, 가위는 종이를 이기고, 종이는 발굽을 이깁니다. 만약 같은 것을 낸다면, 동점처리 됩니다.

 

농부 존은 "발굽, 종이, 가위" 게임에서 상을 탄 소 베시와 경기하기를 원한다. 게임은 총 N(1≤N≤100,000)개의 라운드로 이루어져 있고,이 게임의 전문가인 베시는 Farmer John이 행동하기 전에 각각의 제스처를 예측할 수 있다. 그러나, 소인 베시는 매우 게으르다. 그렇기에 베시는 같은 동작을 여러 번 연속으로 내는 경향이 있다. 베시는 게임 전체에 걸쳐 최대 한 번만 제스처를 바꾸려고 한다. 예를 들어, 처음 x게임에서 "발굽"을 내면, 나머지 N-x 게임에서 "종이"로 전환할 수 있습니다.

 

 

- 알고리즘 정리

 

왼쪽과 오른쪽을 나눠서 Hoof, Paper, Scissors의 최대 개수의 합을 저장하고, 그 값이 result보다 크다면 result를 갱신해 주는 형식으로 진행했습니다.

(DP라고 하기엔 살짝 애드혹 형식으로 푼 느낌이 없지않아 있는)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,result,arr[3][100001],l,r;
char c;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c;
		for(int j=0;j<3;j++){
			arr[j][i]+=arr[j][i-1];
		}
		arr[(c-'A')/8][i]++;
	}
	for(int i=1;i<=n;i++){
		l=0,r=0;
		for(int j=0;j<3;j++){
			if(l<arr[j][i]){
				l=arr[j][i];
			}
			if(r<arr[j][n]-arr[j][i]){
				r=arr[j][n]-arr[j][i];
			}
		}
		if(result<l+r){
			result=l+r;
		}
	}
	cout<<result;
}

코드 제출 결과