์˜ฅ์ƒ ์ •์› ๊พธ๋ฏธ๊ธฐ 1

[Baekjoon] 6198_์˜ฅ์ƒ ์ •์› ๊พธ๋ฏธ๊ธฐ

Gold V๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/6198)๋ฌธ์ œ  ๋„์‹œ์—๋Š” N๊ฐœ์˜ ๋นŒ๋”ฉ์ด ์žˆ๋‹ค.๋นŒ๋”ฉ ๊ด€๋ฆฌ์ธ๋“ค์€ ๋งค์šฐ ์„ฑ์‹คํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ๋‹ค๋ฅธ ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ ์ •์›์„ ๋ฒค์น˜๋งˆํ‚นํ•˜๊ณ  ์‹ถ์–ด ํ•œ๋‹ค.i๋ฒˆ์งธ ๋นŒ๋”ฉ์˜ ํ‚ค๊ฐ€ hi์ด๊ณ , ๋ชจ๋“  ๋นŒ๋”ฉ์€ ์ผ๋ ฌ๋กœ ์„œ ์žˆ๊ณ  ์˜ค๋ฅธ์ชฝ์œผ๋กœ๋งŒ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.i๋ฒˆ์งธ ๋นŒ๋”ฉ ๊ด€๋ฆฌ์ธ์ด ๋ณผ ์ˆ˜ ์žˆ๋Š” ๋‹ค๋ฅธ ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ ์ •์›์€ i+1, i+2,.... , N์ด๋‹ค.๊ทธ๋Ÿฐ๋ฐ ์ž์‹ ์ด ์œ„์น˜ํ•œ ๋นŒ๋”ฉ๋ณด๋‹ค ๋†’๊ฑฐ๋‚˜ ๊ฐ™์€ ๋นŒ๋”ฉ์ด ์žˆ์œผ๋ฉด ๊ทธ๋‹ค์Œ์— ์žˆ๋Š” ๋ชจ๋“  ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ์€ ๋ณด์ง€ ๋ชปํ•œ๋‹ค.์˜ˆ) N=6, H = {10, 3, 7, 4, 12, 2}์ธ ๊ฒฝ์šฐ1๋ฒˆ ๊ด€๋ฆฌ์ธ์€ 2, 3, 4๋ฒˆ ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.2๋ฒˆ ๊ด€๋ฆฌ์ธ์€ ๋‹ค๋ฅธ ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ์„ ํ™•์ธํ•  ์ˆ˜ ์—†๋‹ค.3๋ฒˆ ๊ด€๋ฆฌ์ธ์€ 4๋ฒˆ ๋นŒ๋”ฉ์˜ ์˜ฅ์ƒ์„ ํ™•์ธํ•  ..