[Baekjoon] - 1149. RGB๊ฑฐ๋ฆฌ (G4)

์˜ค๋™ํ›ˆยท2022๋…„ 3์›” 13์ผ
0

Baekjoon

๋ชฉ๋ก ๋ณด๊ธฐ
57/58
post-thumbnail

1. Problem ๐Ÿ“ƒ

๐Ÿ“š ์ถœ์ฒ˜ - 1149 - RGB๊ฑฐ๋ฆฌ

๋ฌธ์ œ ์„ค๋ช…
RGB๊ฑฐ๋ฆฌ์—๋Š” ์ง‘์ด N๊ฐœ ์žˆ๋‹ค. ๊ฑฐ๋ฆฌ๋Š” ์„ ๋ถ„์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๊ณ , 1๋ฒˆ ์ง‘๋ถ€ํ„ฐ N๋ฒˆ ์ง‘์ด ์ˆœ์„œ๋Œ€๋กœ ์žˆ๋‹ค.

์ง‘์€ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘ ์ค‘ ํ•˜๋‚˜์˜ ์ƒ‰์œผ๋กœ ์น ํ•ด์•ผ ํ•œ๋‹ค. ๊ฐ๊ฐ์˜ ์ง‘์„ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘์œผ๋กœ ์น ํ•˜๋Š” ๋น„์šฉ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์•„๋ž˜ ๊ทœ์น™์„ ๋งŒ์กฑํ•˜๋ฉด์„œ ๋ชจ๋“  ์ง‘์„ ์น ํ•˜๋Š” ๋น„์šฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด๋ณด์ž.

  • 1๋ฒˆ ์ง‘์˜ ์ƒ‰์€ 2๋ฒˆ ์ง‘์˜ ์ƒ‰๊ณผ ๊ฐ™์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค.
  • N๋ฒˆ ์ง‘์˜ ์ƒ‰์€ N-1๋ฒˆ ์ง‘์˜ ์ƒ‰๊ณผ ๊ฐ™์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค.
  • i(2 โ‰ค i โ‰ค N-1)๋ฒˆ ์ง‘์˜ ์ƒ‰์€ i-1๋ฒˆ, i+1๋ฒˆ ์ง‘์˜ ์ƒ‰๊ณผ ๊ฐ™์ง€ ์•Š์•„์•ผ ํ•œ๋‹ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ์ง‘์˜ ์ˆ˜ 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

2. Logic ๐Ÿ‘จโ€๐Ÿซ

์ฒ˜์Œ์— ์ด ๋ฌธ์ œ๋ฅผ ์ ‘ํ–ˆ์„ ๋•Œ ์ดํ•ด๊ฐ€ ์ž˜ ์•ˆ๊ฐ€์„œ ๋‹ค๋ฅธ ํ•ด๊ฒฐํ•˜์‹  ๋ถ„์˜ ๊ธ€์„ ์ฐธ๊ณ ํ–ˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ์•Œ๊ณ ๋‚˜๋‹ˆ ํ•ด๊ฒฐํ•˜๋Š”๋ฐ๋Š” ๋ฌด์ฒ™ ๊ฐ„๋‹จํ–ˆ๋‹ค.

์ฒซ ๋ฒˆ์งธ ์ค„์€ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘์œผ๋กœ ์น ํ•˜๋Š” ๋น„์šฉ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ์ด๊ณ , ๊ทœ์น™๋Œ€๋กœ ๋ชจ๋“  ์ง‘์„ ์น ํ•ด ๋‚˜๊ฐˆ ๋•Œ ์ตœ์†Œํ•œ์˜ ๋น„์šฉ์„ ์ฐพ์•„๋ผ

์•„ ์ด๊ฒŒ ๋ฌธ์ œ์— ๋‚˜์™€์žˆ๋Š”๊ฑฐ๋ž‘ ๋น„์Šทํ•œ๋ฐ ์ผ๋‹จ ๋ด๋ณด์ž

RGB
1๋ฒˆ264083
2๋ฒˆ496057
๊ณ„์‚ฐ49 + min(1๋ฒˆ G, 1๋ฒˆ B)60 + min(1๋ฒˆ R, 1๋ฒˆ B)57 + min(1๋ฒˆ R, 1๋ฒˆ G)
=898683
3๋ฒˆ138999
๊ณ„์‚ฐ13 + min(2๋ฒˆ ๊ณ„์‚ฐ G, 2๋ฒˆ ๊ณ„์‚ฐ B)89 + min(2๋ฒˆ ๊ณ„์‚ฐ R, 2๋ฒˆ ๊ณ„์‚ฐ B)99 + min(2๋ฒˆ ๊ณ„์‚ฐ R, 2๋ฒˆ ๊ณ„์‚ฐ G)
=96172182

๋”ฐ๋ผ์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฒฐ๊ณผ๋Š” 96์ด ๋‚˜์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

3. Code ๐Ÿ’ป

1. ๋‚ด๊ฐ€ ํ‘ผ ์ฝ”๋“œ ๐Ÿ˜

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]))
profile
์‚ฝ์งˆ์˜ ๊ธฐ๋ก๋“ค๐Ÿฅ

0๊ฐœ์˜ ๋Œ“๊ธ€