deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ๋ฐฑ์ค€ - 1890. ์ ํ”„
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 1890. ์ ํ”„

2020. 10. 12. 08:01
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

  • S2 | DP

DFS๋กœ ํ•ด๋ดค์ง€๋งŒ ์—ญ์‹œ๋‚˜ ์‹œ๊ฐ„์ดˆ๊ณผ!!

์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(N^2) ์ธ DP๋กœ ํ’€์–ด๋ดค๋‹ค.

 

dp์—๋Š” ํ˜„์žฌ ์œ„์น˜๊นŒ์ง€ ์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋‹ด์•„์„œ ํ•ด๊ฒฐํ•จ.

 

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

N = int(input())
field = [list(map(int, input().split())) for _ in range(N)]
answer = 0

dp = [[0] * N for _ in range(N)]  # i,j๊นŒ์ง€ ์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ €์žฅ
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        if i == N - 1 and j == N - 1:  # ๋์— ๋„๋‹ฌํ–ˆ์„ ๋•Œ
            print(dp[i][j])
            break
        cur_cnt = field[i][j]
        # ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ฐ€๊ธฐ
        if j + cur_cnt < N:
            dp[i][j + cur_cnt] += dp[i][j]
        # ์•„๋ž˜๋กœ ๊ฐ€๊ธฐ
        if i + cur_cnt < N:
            dp[i + cur_cnt][j] += dp[i][j]

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: BACKJOON ONLINE JUDGE

๋งํฌ: https://www.acmicpc.net/problem/1890

 

1890๋ฒˆ: ์ ํ”„

์ฒซ์งธ ์ค„์— ๊ฒŒ์ž„ ํŒ์˜ ํฌ๊ธฐ N (4 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ทธ ๋‹ค์Œ N๊ฐœ ์ค„์—๋Š” ๊ฐ ์นธ์— ์ ํ˜€์ ธ ์žˆ๋Š” ์ˆ˜๊ฐ€ N๊ฐœ์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์นธ์— ์ ํ˜€์žˆ๋Š” ์ˆ˜๋Š” 0๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 9๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋ฉฐ, ๊ฐ€์žฅ ๏ฟฝ๏ฟฝ

www.acmicpc.net

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] ๋ฐฑ์ค€ - 1965. ์ƒ์ž ๋„ฃ๊ธฐ  (0) 2020.10.14
[python] ๋ฐฑ์ค€ - 2504. ๊ด„ํ˜ธ์˜ ๊ฐ’  (0) 2020.10.13
[python] ๋ฐฑ์ค€ - 1780. ์ข…์ด์˜ ๊ฐœ์ˆ˜  (0) 2020.10.11
[python] ๋ฐฑ์ค€ - 11279. ์ตœ๋Œ€ ํž™  (0) 2020.10.10
[python] ๋ฐฑ์ค€ - 10819. ์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœ  (0) 2020.10.09
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [python] ๋ฐฑ์ค€ - 1965. ์ƒ์ž ๋„ฃ๊ธฐ
    • [python] ๋ฐฑ์ค€ - 2504. ๊ด„ํ˜ธ์˜ ๊ฐ’
    • [python] ๋ฐฑ์ค€ - 1780. ์ข…์ด์˜ ๊ฐœ์ˆ˜
    • [python] ๋ฐฑ์ค€ - 11279. ์ตœ๋Œ€ ํž™
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”