๐ ์ถ์ฒ - 1149 - RGB๊ฑฐ๋ฆฌ
๋ฌธ์ ์ค๋ช
RGB๊ฑฐ๋ฆฌ์๋ ์ง์ด N๊ฐ ์๋ค. ๊ฑฐ๋ฆฌ๋ ์ ๋ถ์ผ๋ก ๋ํ๋ผ ์ ์๊ณ , 1๋ฒ ์ง๋ถํฐ N๋ฒ ์ง์ด ์์๋๋ก ์๋ค.
์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋ ์ค ํ๋์ ์์ผ๋ก ์น ํด์ผ ํ๋ค. ๊ฐ๊ฐ์ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด ์ฃผ์ด์ก์ ๋, ์๋ ๊ท์น์ ๋ง์กฑํ๋ฉด์ ๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ์ ๊ตฌํด๋ณด์.
์
๋ ฅ
์ฒซ์งธ ์ค์ ์ง์ ์ N(2 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด 1๋ฒ ์ง๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ง์ ์น ํ๋ ๋น์ฉ์ 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ |
---|---|
3 26 40 83 49 60 57 13 89 99 | 96 |
3 1 100 100 100 1 100 100 100 1 | 3 |
3 1 100 100 100 100 100 1 100 100 | 102 |
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91 | 208 |
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19 | 253 |
์ฒ์์ ์ด ๋ฌธ์ ๋ฅผ ์ ํ์ ๋ ์ดํด๊ฐ ์ ์๊ฐ์ ๋ค๋ฅธ ํด๊ฒฐํ์ ๋ถ์ ๊ธ์ ์ฐธ๊ณ ํ๋ค. ๋ฌธ์ ๋ฅผ ์๊ณ ๋๋ ํด๊ฒฐํ๋๋ฐ๋ ๋ฌด์ฒ ๊ฐ๋จํ๋ค.
์ฒซ ๋ฒ์งธ ์ค์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด ์ฃผ์ด์ก์ ๋์ด๊ณ , ๊ท์น๋๋ก ๋ชจ๋ ์ง์ ์น ํด ๋๊ฐ ๋ ์ต์ํ์ ๋น์ฉ์ ์ฐพ์๋ผ
์ ์ด๊ฒ ๋ฌธ์ ์ ๋์์๋๊ฑฐ๋ ๋น์ทํ๋ฐ ์ผ๋จ ๋ด๋ณด์
R | G | B | |
---|---|---|---|
1๋ฒ | 26 | 40 | 83 |
2๋ฒ | 49 | 60 | 57 |
๊ณ์ฐ | 49 + min(1๋ฒ G, 1๋ฒ B) | 60 + min(1๋ฒ R, 1๋ฒ B) | 57 + min(1๋ฒ R, 1๋ฒ G) |
= | 89 | 86 | 83 |
3๋ฒ | 13 | 89 | 99 |
๊ณ์ฐ | 13 + min(2๋ฒ ๊ณ์ฐ G, 2๋ฒ ๊ณ์ฐ B) | 89 + min(2๋ฒ ๊ณ์ฐ R, 2๋ฒ ๊ณ์ฐ B) | 99 + min(2๋ฒ ๊ณ์ฐ R, 2๋ฒ ๊ณ์ฐ G) |
= | 96 | 172 | 182 |
๋ฐ๋ผ์ ๋ค์๊ณผ ๊ฐ์ด ๊ฒฐ๊ณผ๋ 96
์ด ๋์ค๊ฒ ๋ฉ๋๋ค.
import sys
read = sys.stdin.readline
N = int(read())
cache =[list(map(int, read().split())) for _ in range(N)]
for i in range(1, N):
cache[i][0] += min(cache[i-1][1], cache[i-1][2])
cache[i][1] += min(cache[i-1][0], cache[i-1][2])
cache[i][2] += min(cache[i-1][0], cache[i-1][1])
print(min(cache[-1]))