[2118] 두 개의 탑

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

2118번: 두 개의 탑

투포인터 문제다.

 

풀이

문제에 주어지는 두 지점사이의 거리는 시계방향과 반시계 방향 중 짧은 쪽이 거리가 된다고 한다. 즉 시계방향 기준 반시계 방향 거리라 함은 (전체 길이 - 시계방향 거리) 로 계산이 가능하며 해당 지점의 거리는 둘 중 적은 거리로 정해진다는 것이다.

 

시작 인덱스와 끝 인덱스를 생성하여 구간의 길이를 측정한다. 구간의 길이가 최대거리보다 짧거나 같다면, 끝 인덱스를 한칸 늘린다. 반대로 현재 구간의 길이가 최대값보다 크다면, 시작 인덱스를 증가한다. 

 

정답 코드

	mport Foundation
	let n = Int(readLine()!)!
	var arr = [Int]()
	var ans = 0
	var total = 0
	for _ in 0..<n{
	let num = Int(readLine()!)!
	arr.append(num)
	total += num
	}
	var head = 0
	var tail = 0
	var sum = 0
	while true{
	if sum > ans{
	sum -= arr[head]
	head += 1
	}else if tail == n{
	break
	}else{
	sum += arr[tail]
	tail += 1
	}
	ans = max(ans, min(sum,total-sum))
	}
	print(ans)

view raw 2118.swift hosted with ❤ by GitHub