[BOJ 20493] 세상은 하나의 손수건

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

20493번: 세상은 하나의 손수건

 

- 문제 요약

 

준원이가 방향을 바꾼 횟수 n, 걸어간 시간 t가, n개의 줄에 방향을 바꾼 시간, 방향이 주어진다.

t초에 지정된 방향으로 한 칸씩 이동하고 방향은 왼쪽, 오른쪽 중 하나로만 바꿀 수 있다.

처음에 오른쪽 방향으로 갈 때 t초 후에 준원이의 위치 좌표를 구하시오.

 

 

- 알고리즘 정리

 

Tast case 1, 2를 가져와서 시뮬레이션 해보며 정리하겠습니다.

 

Tast case 1

I : 0 100

O : 100 0

 

Tast case 2

I : 3 100

   30 right

   50 right 

   60 left

O : 20 -60

 

1번 같은 경우에는 출력이 100 0 으로 나오는걸 볼 수 있습니다.

처음에 시작 방향이 오른쪽이니 (0,0)에서 (100,0)까지 쭉 이동하게 됩니다.

 

2번 같은 경우에는 문제에 첨부되어있던 사진을 보면서 생각해보겠습니다.

 

Tast case 2번 풀이

우선 처음 출발 할 때 (0,0)에서 시작하고 오른쪽 방향으로 30만큼 가게 되니 좌표는 (30,0)이 됩니다.

그리고 전환할 방향이 "right"이니 오른쪽으로 방향을 바꾸게 됩니다.

 

이제 아래 방향으로  30초부터 50초까지 총 20초동안 움직이게 됩니다.

그러므로 좌표는 (30,-20)이 됩니다.

 

방향을 오른쪽으로 전환하고 같은 방법으로 좌표를 이동하면 좌표는 (20,-20)이 됩니다.

 

이 좌표에 오기까지 걸린 시간은 주어진 시간 100초 중 60초입니다.

남은 40초동안은 정해진 방향에서 쭉 직진을 해야 최종 좌표가 나오게 됩니다.

 

그러므로 최종 좌표는 (20,-60)입니다.

 

어떤 식으로 흐름이 흘러가는지는 알았으니 어떻게 코드를 짤지 생각해보겠습니다.

 

우선 현재 방향을 지정해주는 변수 하나가 필요 할 것 같습니다.

또한 n개의 줄에 걸쳐서 입력될 시간과 방향을 담을 pair를 선언해주면 좋을 것 같습니다.

마지막에 방향을 바꾸지 않고 쭉 직진을 하는 경우도 있을테니 여태까지 쓴 시간을 담을 변수도 필요합니다.

당연히 좌표값인 x, y도 필요합니다.

 

위의 내용을 바탕으로 정리한 알고리즘은 아래와 같습니다.

 

1부터 n까지 루프를 돌리고 방향 변수에 따라서 방향을 바꾸며 좌표값을 바꿉니다.

가장 처음 나온 0번째 줄의 시간과 방향은  x or y에 그냥 더하면 될 것이고,

그 뒤로 나온 시간들은 i번째(현재) 시간에서 i-1번째 시간을 빼서 좌표값에 방향에 따라 더합니다.

sum에 현재 좌표값에 더한 시간 만큼 더해가며 끝까지 루프를 돌리고 나옵니다.

 

t-sum(주어진 시간-쓴 시간=남은 시간)이 0이 아니라면 방향에 따라 남은 시간만큼 좌표값을 바꿉니다.

 

그리고 좌표값 x, y를 출력하면 답이 나올 것입니다.

 

이제 이 알고리즘을 코드로 짜보겠습니다.

 

 

- 코드 작성

 

T의 범위가 1 ≤ T ≤ 1,000,000,000로 나와있으니 long long형으로 선언을 해야 할텐데

일일히 치기 귀찮으니 typedef를 써서 ll로 바꿔 코딩하겠습니다.

또한, 방향 변수인 w를 0,1,2,3(왼쪽, 오른쪽, 위쪽, 아래쪽)으로 바꿔가며 현재 방향을 표시하겠습니다.

 

#include<cstdio>
#include<iostream>
using namespace std;

typedef long long ll;
ll n,t,x,y,w=1,sum;//0,1,2,3 : 왼오위아 
pair<ll,string>arr[100001];

int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	for(int i=1;i<=n;i++){
		if(i==0){
			x+=arr[i].first;
			sum+=arr[i].first;
			if(arr[i].second=="right"){
				w=3;
			}
			else{
				w=2;
			}	
		}
		else{
			if(w==0){
				x-=(arr[i].first-arr[i-1].first);
				sum+=arr[i].first-arr[i-1].first;
				if(arr[i].second=="right"){
					w=2;
				}
				else{
					w=3;
				}
			} 
			else if(w==1){
				x+=(arr[i].first-arr[i-1].first);
				sum+=arr[i].first-arr[i-1].first;
				if(arr[i].second=="right"){
					w=3;
				}
				else{
					w=2;
				}
			}
			else if(w==2){
				y+=(arr[i].first-arr[i-1].first);
				sum+=arr[i].first-arr[i-1].first;
				if(arr[i].second=="right"){
					w=1;
				}
				else{
					w=0;
				}
			}
			else{
				y-=(arr[i].first-arr[i-1].first);
				sum+=arr[i].first-arr[i-1].first;
				if(arr[i].second=="right"){
					w=0;
				}
				else{
					w=1;
				}
			}
		}
	}
	if(n==0){
		cout<<t<<" "<<0;
	}
	else{
		sum=t-sum;
		if(sum<t){
			if(w==0){
				x-=sum;
			}
			else if(w==1){
				x+=sum;
			}
			else if(w==2){
				y+=sum;
			}
			else if(w==3){
				y-=sum;
			}
		}
		cout<<x<<" "<<y;
	}
}

코드 제출 결과

그저 복붙의 향현인 간단한 구현 문제였습니다.