BOJ 25711 : 인경산

#BOJ 25711 : 인경산

25711번: 인경산

#풀이

문제 이해력이 딸리는 것 같다... 맨 처음에는 무조건 산장을 거쳐서 가야하는지 몰라서 엄청 빠르게 구현했다가 다시 읽어보니 인접한 산장 사이에 코스가 있는 거 였다....

 

문제에서 그림도 보여주길래 왜 저렇게 보여준거지 하면서 읽었는데 ㅋㅋㅋㅋ

 

일단 dp? 와 비슷한 문제이다. 알고리즘 태그 보니까 누적합이라고 나와있네...!

 

산장을 입력 받을 때 마다 계산하면 시간초과가 뜬다.

 

1번산장에서 N번산장까지는 비용과 N번 산장에서 1번산장까지 비용을 저장하고 입력 시 그냥 출력만 해야 한다.

1-2

1-3

1-4

1-5

1-6

이렇게 저장하고 2-6 의 비용을 출력해야 하면 6의 비용 - 2의 비용 을 하면 2에서 6의 비용이 나온다.

 

또한

6-5

6-4

6-3

6-2

6-1

이렇게 하여 구현하면 된다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int dx[200001];
int dy[200001];
double d_up[200001];
double d_do[200001];
int n, m;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <=n; i++){
		cin>>dx[i];
	}
	for(int i = 1; i <=n; i++){
		cin>>dy[i];
	}
	
	for(int i= 1; i < n; i++){
		int j = i+1;
		double dis = sqrt(pow(dx[i] - dx[j], 2) + pow(dy[i] - dy[j], 2));
		if(dy[j] > dy[i])
		{	
			d_up[j] = d_up[i] + dis * 3;
		}
		else if(dy[j] == dy[i])
		{	
			d_up[j] = d_up[i] + dis * 2;
			
		}
		else{
			d_up[j] = d_up[i] + dis;
			
		}
	}
	for(int i= n; i > 1; i--){
		int j = i-1;
		double dis = sqrt(pow(dx[i] - dx[j], 2) + pow(dy[i] - dy[j], 2));
		if(dy[j] > dy[i])
		{	
			d_do[j] = d_do[i] + dis * 3;
		}
		else if(dy[j] == dy[i])
		{	
			d_do[j] = d_do[i] + dis * 2;
			
		}
		else{
			d_do[j] = d_do[i] + dis;
			
		}
	}

	for(int i = 1; i <=m; i++){
		int a, b;
		long double ans = 0;
		cin >> a >> b;
		if(a < b){
			ans = d_up[b] - d_up[a];
		}
		
		else{
			ans = d_do[b] - d_do[a];
		}
		cout << ans << '\n';
		
	}
	return 0;
}