c언어 12841번 정보대 등산 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	
	long long arr[n], left[n], right[n], tmp = n-1; //변수들과 배열들
	for(int i=0; i<n; i++) scanf("%lld", &arr[i]); //n개의 횡단보도 길이
	
	left[0] = right[tmp] = 0; //왼쪽 시작지점과 오른쪽 마지막 지점은 길이가 0 입니다.
	for(int i=1; i<n; i++) { //왼쪽 이동 길이
		scanf("%lld", &left[i]);
		left[i] += left[i-1]; //이전의 값을 더해줍니다.
	}
	for(int i=0; i<tmp; i++) scanf("%lld", &right[i]); //오른쪽 이동 길이
	for(int i=tmp-1; i>=0; i--) right[i] += right[i+1]; //반대로 더해줍니다.
	
	long long min = 1e16, key=0; //min은 최솟값을, key는 최소 길이의 길의 번호를 저장하는 변수
	for(int i=0; i<n; i++) {
		long long tmp = left[i] + right[i] + arr[i]; //왼쪽 이동길이 + 오른쪽 이동길이 + 횡단보도 길이
		if(min > tmp) { //작다면?
			key = i+1;
			min = tmp;
		}
	}
	printf("%lld %lld", key, min); //최소길이일 떄의 번호와 그때의 최소값을 출력합니다.
}

 

풀이 : 누적합

 

이 문제는

 

횡단보도를 건너기 전까지의 왼쪽 이동길이 (초기값 0)

횡단보도의 길이

횡단보도를 건넌 이후 오른쪽 이동길이 (마지막 값이 0)

 

을 더한 다음 이 중 가장 작은 값과, 이때의 번호를 출력하면 되는 문제입니다.

 

왼쪽 이동길이는, 누적합을 이용해, 이전의 길이를 계속 더해주며

오른쪽 이동길이는, 누적합을 이용하는 것은 같으나, 왼쪽과는 방향이 반대이므로  맨마지막 것부터 이전 값에 누적 시켜줍니다.

 

그런 다음 왼쪽의 길이 + 횡단보도의 길이 + 오른쪽의 길이 중 가장 값이 적은 것을 찾으면 됩니다.

 

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

12841번: 정보대 등산