[BOJ 27560] Moo Route

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

27560번: Moo Route

 

- 문제 요약

 

Farmer Nhoj는 Bessie를 외딴 길에 떨어뜨려놨습니다.

Bessie의 현재 시간은 t=0초이고, 현재 위치는 x=0입니다.

Bessie는 방향을 바꿔가며 왼쪽 혹은 오른쪽으로 이동할 수 있습니다.(왼쪽으로 갈 때는 L, 오른쪽으로 갈 때는 R을 출력해 줍니다.)

 

Bessie가 방향 변경을 최소화해서 출구까지 가는 경로를 찾아주세요.(경로가 여러 개라면 그중 아무것이나 출력해 주세요.)

 

 

- 알고리즘 정리

 

방향을 바꿔야 할 때까지 현재 진행 방향으로 움직이며 그리디게하게 해결해 주면 됩니다.

(Bessie의 초기 진행 방향은 오른쪽입니다.)

 

 

- 코드 작성

 

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

typedef long long ll;
string s="";
ll n,arr[100001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	ll i=0;
	while(!(i==0&&arr[i]==0)){
		while(arr[i]>0){
			s+="R";
			arr[i++]--;
		}
		while(i>0&&(arr[i-1]>1||arr[i]==0)){
			s+="L";
			arr[--i]--;
		}
	}
	cout<<s;
}

코드 제출 결과