C ๋ฒ ๋ฌธ์ : ์ค ์ธ์ฐ๊ธฐ. ์์คํ์ผ ์ด๋ฆ : ccc.c or ccc.cpp
์ ์น์์ N๋ช
์ ์์ด๋ค์ด ์๋ค. ์ค๋์ ์ํ์ ๊ฐ๋ ๋ ์ด๋ค. ์ ์๋์ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ๋ฒํธ๊ฐ ์ ํ์๋ ๋ฒํธํ๋ฅผ ์์ด๋ค์ ๊ฐ์ด์ ๋ถ์ฌ์ฃผ์๋ค. ์ ์๋์ ์์ด๋ค์ ํจ๊ณผ์ ์ผ๋ก ๋ณดํธํ๊ธฐ ์ํด ๋ชฉ์ ์ง๊น์ง ๋ฒํธ์์๋๋ก ์ผ๋ ฌ๋ก ์์ ๊ฑธ์ด๊ฐ๋๋ก ํ์๋ค. ์ด๋ ๋์ค์ ๋ณด๋ ์์ด๋ค์ ๋ฒํธ์์๊ฐ ๋ฐ๋์๋ค. ๊ทธ๋์ ์ ์๋์ ๋ค์ ๋ฒํธ ์์๋๋ก ์ค์ ์ธ์ฐ๊ธฐ ์ํด์ ์์ด๋ค์ ์์น๋ฅผ ์ฎ๊ธฐ๋ ค๊ณ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์์ด๋ค์ด ํผ๋์ค๋ฌ์ํ์ง ์๋๋ก ํ๊ธฐ ์ํด ์์น๋ฅผ ์ฎ๊ธฐ๋ ์์ด๋ค์ ์๋ฅผ ์ต์๋ก ํ๋ ค๊ณ ํ๋ค.
์๋ฅผ ๋ค์ด, 7๋ช ์ ์์ด๋ค์ด ๋ค์๊ณผ ๊ฐ์ด ์์๋๋ก ์ค์ ์ ์๋ค๊ณ ํ์.
์๋ฅผ ๋ค์ด, 7๋ช ์ ์์ด๋ค์ด ๋ค์๊ณผ ๊ฐ์ด ์์๋๋ก ์ค์ ์ ์๋ค๊ณ ํ์.
3 7 5 2 6 1 4
์์ด๋ค์ ์์๋๋ก ์ค์ ์ธ์ฐ๊ธฐ ์ํด, ๋จผ์ 4๋ฒ ์์ด๋ฅผ 7๋ฒ ์์ด์ ๋ค๋ก ์ฎ๊ฒจ๋ณด์. ๊ทธ๋ฌ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์์๊ฐ ๋๋ค.3 7 4 5 2 6 1
์ด์ , 7๋ฒ ์์ด๋ฅผ ๋งจ ๋ค๋ก ์ฎ๊ธด๋ค.3 4 5 2 6 1 7
๋ค์, 1๋ฒ ์์ด๋ฅผ ๋งจ ์์ผ๋ก ์ฎ๊ธด๋ค.1 3 4 5 2 6 7
๋ง์ง๋ง์ผ๋ก 2๋ฒ ์์ด๋ฅผ 1๋ฒ ์์ด์ ๋ค๋ก ์ฎ๊ธฐ๋ฉด ๋ฒํธ ์์๋๋ก ๋ฐฐ์น๋๋ค.1 2 3 4 5 6 7
์์ ๋ฐฉ๋ฒ์ผ๋ก๋ ๋ชจ๋ ๋ค ๋ช
์ ์์ด๋ฅผ ์ฎ๊ฒจ ๋ฒํธ ์์๋๋ก ์ค์ ์ธ์ด๋ค. ์์ ์์์ ์ธ๋ช
์ ์์ด๋ง์ ์ฎ๊ฒจ์๋ ์์๋๋ก ๋ฐฐ์นํ ์ ๊ฐ ์๋ค. ๋ฐ๋ผ์ ๋ค ๋ช
์ ์ฎ๊ธฐ๋ ๊ฒ์ด ๊ฐ์ฅ ์ ์ ์์ ์์ด๋ฅผ ์ฎ๊ธฐ๋ ๊ฒ์ด๋ค.N๋ช ์ ์์ด๋ค์ด ์์์ ์์๋ก ์ค์ ์ ์์ ๋, ๋ฒํธ ์์๋๋ก ๋ฐฐ์นํ๊ธฐ ์ํด ์ฎ๊ฒจ์ง๋ ์์ด์ ์ต์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ ¶
์
๋ ฅ์ ํ์ค ์
๋ ฅ์ด๋ค. ์
๋ ฅ์ ์ฒซ์ค์ ํ
์คํธ ์ผ์ด์ค์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ T(10 ์ดํ)๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ ์ค ๋ถํฐ T๊ฐ์ ํ
์คํธ ์ผ์ด์ค๊ฐ ์ฃผ์ด์ง๋ค. ํ
์คํธ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ์์ด๋ค์ ์ N์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ N๋ช
์ ์์ด๋ค์ ์์๋ฅผ ๋ํ๋ด๋, 1๋ถํฐ N ์ฌ์ด์ ์ ์๋ก ์ด๋ค์ง ์์ด์ด ์ฃผ์ด์ง๋ค. ์์ด์์ ์ ์ ์ฌ์ด์๋ ๋น์นธ์ด ํ๋ ๋ค์ด ์๋ค. N์ 2์ด์ 200์ดํ์ ์ ์์ด๋ค.
์ถ๋ ฅ ¶
์ถ๋ ฅ์ ํ์ค ์ถ๋ ฅ์ด๋ค. ์ถ๋ ฅ์ T์ค๋ก ์ด๋ค์ง๋ค. ๊ฐ ํ
์คํธ ์ผ์ด์ค์ ๋ํด์ ๋ฒํธ ์์๋๋ก ์ค์ ์ธ์ฐ๋๋ฐ ์ฎ๊ฒจ์ง๋ ์์ด๋ค์ ์ต์ ์๋ฅผ ์ถ๋ ฅํ๋ค. T๊ฐ์ ํ
์คํธ ์ผ์ด์ค๋ฅผ ๋ชจ๋ ๋งํ์ผ ์ด ๋ฌธ์ ๋ฅผ ๋งํ ๊ฒ์ด๋ค.
์ ๋ ฅ์ ์ ¶
~cpp 3 7 3 7 5 2 6 1 4 6 6 5 4 3 2 1 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
์ ๋ ฅ์ ์์ ๋ํ ์ถ๋ ฅ ¶
~cpp 4 5 0