[python]๋ฐฑ์ค€ 1780๋ฒˆ : ์ข…์ด์˜ ๊ฐœ์ˆ˜
Algorithm ๋ฌธ์ œ/BOJ 2020. 3. 6. 22:26

์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ 2 ์ดˆ 256 MB 9503 5463 4173 58.667% ๋ฌธ์ œ N×Nํฌ๊ธฐ์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ์ข…์ด๊ฐ€ ์žˆ๋‹ค. ์ข…์ด์˜ ๊ฐ ์นธ์—๋Š” -1, 0, 1์˜ ์„ธ ๊ฐ’ ์ค‘ ํ•˜๋‚˜๊ฐ€ ์ €์žฅ๋˜์–ด ์žˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์ด ํ–‰๋ ฌ์„ ์ ์ ˆํ•œ ํฌ๊ธฐ๋กœ ์ž๋ฅด๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์ด๋•Œ ๋‹ค์Œ์˜ ๊ทœ์น™์— ๋”ฐ๋ผ ์ž๋ฅด๋ ค๊ณ  ํ•œ๋‹ค. ๋งŒ์•ฝ ์ข…์ด๊ฐ€ ๋ชจ๋‘ ๊ฐ™์€ ์ˆ˜๋กœ ๋˜์–ด ์žˆ๋‹ค๋ฉด ์ด ์ข…์ด๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•œ๋‹ค. (1)์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” ์ข…์ด๋ฅผ ๊ฐ™์€ ํฌ๊ธฐ์˜ 9๊ฐœ์˜ ์ข…์ด๋กœ ์ž๋ฅด๊ณ , ๊ฐ๊ฐ์˜ ์ž˜๋ฆฐ ์ข…์ด์— ๋Œ€ํ•ด์„œ (1)์˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ์ด์™€ ๊ฐ™์ด ์ข…์ด๋ฅผ ์ž˜๋ž์„ ๋•Œ, -1๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜, 0์œผ๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜, 1๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ด๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1≤N≤3^7, N์€ 3^..