[백준] 1890번: 점프 - Kotlin[코틀린]

2023. 9. 27. 22:39·알고리즘/Baekjoon

문제

 

 

1890번: 점프

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장

www.acmicpc.net

 


풀이

 

 문제는 시작점부터 도착점까지 도달 가능한 경로 수를 구하는 것이다. 처음엔 DFS로 시도했지만 시간초과가 발생하여 반복문과 DP를 활용한 풀이를 하였다.

 

 시작점인 dp[0][0]에 1을 할당하고, 반복문을 통해 각 위치까지의 도달 가능한 경로 수를 구한다. dp[i][j]가 0인 배열은 처리하지 않고 넘어가도록 하며 0이 아닌 경우에는 오른쪽과 아래 방향으로 map[i][j]만큼 이동 한 후, 그 지점의 dp 배열에 현재 위치 경로 수를 더해준다.

 


코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val dx = arrayOf(0, 1)
    val dy = arrayOf(1, 0)

    val num = br.readLine().toInt()
    val map = Array(num){ IntArray(num) }
    val dp = Array(num){ LongArray(num) }

    for(i in 0 until num) {
        val st = StringTokenizer(br.readLine())
        for(j in 0 until num) {
            map[i][j] = st.nextToken().toInt()
        }
    }

    dp[0][0] = 1L

    for(i in 0 until num) {
        for(j in 0 until num) {
            if(i == num - 1 && j == num - 1) continue // 도착 지점은 처리하지 않음
            if(dp[i][j] == 0L) continue // 도달 불가능한 경로

            val jump = map[i][j]
            for(d in 0 until 2) {
                val nx = i + jump*dx[d]
                val ny = j + jump*dy[d]

                if(nx < 0 || ny < 0 || nx >= num || ny >= num) continue

                dp[nx][ny] += dp[i][j] // 경로 수 업데이트
            }
        }
    }

    bw.write("${dp[num-1][num-1]}")
    bw.flush()
    bw.close()
    br.close()
}

 

 

'알고리즘 > Baekjoon' 카테고리의 다른 글

[백준] 15649 ~ 15666번: N과 M (2) ~ (12) - Kotlin[코틀린]  (0) 2023.09.29
[백준] 15649번: N과 M (1) - Kotlin[코틀린]  (0) 2023.09.28
[백준] 7576번: 토마토 - Kotlin[코틀린]  (0) 2023.09.27
[백준] 1904번: 01타일 - Kotlin[코틀린]  (0) 2023.09.26
[백준] 10971번: 외판원 순회 2 - Kotlin[코틀린]  (0) 2023.09.24
'알고리즘/Baekjoon' 카테고리의 다른 글
  • [백준] 15649 ~ 15666번: N과 M (2) ~ (12) - Kotlin[코틀린]
  • [백준] 15649번: N과 M (1) - Kotlin[코틀린]
  • [백준] 7576번: 토마토 - Kotlin[코틀린]
  • [백준] 1904번: 01타일 - Kotlin[코틀린]
junghoooooon
junghoooooon
  • junghoooooon
    코드팁스
    junghoooooon
  • 전체
    오늘
    어제
    • 전체 (120)
      • 안드로이드 (0)
        • 코드팁스 (0)
      • 유니티 (0)
        • 코드팁스 (0)
      • 알고리즘 (118)
        • 알고리즘 (0)
        • Baekjoon (118)
      • GitHub (0)
      • 티스토리 (2)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      큐
      모듈러 곱셈 역원
      문자열
      분할 정복
      유니온파인드
      분리집합
      우선순위 큐
      크루스칼
      그리디
      티스토리
      dfs
      피보나치
      에라토스테네스의 체
      DP
      브루트포스
      이분 탐색
      그래프 탐색
      BFS
      소수 판정
      MST
      투 포인터
      수학
      구현
      누적 합
      그래프이론
      정렬
      스택
      프림
      재귀
      백트래킹
    • hELLO· Designed By정상우.v4.10.2
    junghoooooon
    [백준] 1890번: 점프 - Kotlin[코틀린]
    상단으로

    티스토리툴바