[BOJ] Ruby 백준 게똥벌레(3020)

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

 

누적합을 이용하여 푸는 문제이다.

특이하게 시작점과 끝점만을 표시한 후 하나의 누적합 for문으로 끝내는 방식이다.

 

코드는 매우 단순하다.

홀짝을 구분하여 위 아래로 표시를 진행해준다.

오름차순으로 가는 경우, 시작점에 1 | 끝점에 -1로 끝을 표기한다

내림차순의 경우 전체 높이 - 돌 길이 를 한다

결국 누적합으로 for문을 돌게 되면 시작점(돌 시작 위치)로 부터 꼭대기까지 값이 갱신되므로, 

결국 한 배열 안에 몇개의 돌들이 겹치는지를 확인할 수 있다.

N, M = gets.split.map(&:to_i)

graph = Array.new(M,0)

N.times do |i|

  B = gets.to_i

  if i %2 == 0
    graph[0] += 1
    graph[B] -= 1

  else
    graph[M-B] += 1
  end
end

(1...M).each do |i|

  graph[i] += graph[i-1]
end

puts "#{graph.min} #{graph.count(graph.min)}"

 

회고,

이분탐색 문제라해서 이분탐색으로만 접근했는데 누적합으로 더 간단히 풀리는 문제일줄 몰랐다..

한 알고리즘만 보지 말고 다른 알고리즘을 계속 적용하는 능력을 길러야 겠담,..