✍️ 문제 4-2
제8회 소프트웨어(SW) 사고력 올림피아드(초5~6)
※ 다음 문제에 답하시오.
※ 답은 종이에 작성한 뒤 사진으로 제출하세요.
※ 창의적인 생각을 자유롭게 기록해도 됩니다.
문제 4
출발 지점에서 도착 지점까지 로봇이 미로를 탈출하는 게임을 만들려고 한다. 로봇은 오른쪽 또는 아래쪽 방향으로만 이동할 수 있으며 이동한 칸에서 얻은 숫자는 점수로 환산된다.
문제 4-2
각 칸에 표시된 점수가 달라졌을 때, 가장 높은 점수를 얻기 위한 알고리즘을 설계하시오.
[문제 분석]
점수 격자에서 로봇이 이동할 때 가능한 경로의 점수를 비교하고 가장 큰 값을 찾는 경로 최적화 문제입니다.
[예시답안 요약 힌트]
아래와 오른쪽으로 가는 경로의 점수를 비교하고 목적지까지 누적 최고 점수를 저장하세요. 동적 계획법처럼 각 칸의 최고 점수를 쌓아 가면 좋습니다.
가장 높은 점수를 위한 알고리즘 설계:
동적 프로그래밍(DP) 방법을 사용한다:
① dp[i][j] = 출발점에서 (i, j)까지 도달할 수 있는 최대 점수
② 점화식: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + score[i][j]
(위쪽에서 온 경우와 왼쪽에서 온 경우 중 더 큰 값을 선택)
③ 첫 번째 행과 첫 번째 열은 한 방향으로만 올 수 있으므로 순서대로 누적합을 채운다.
④ 최종 도착점 dp[n][m]이 최대 점수가 된다.
이 방법으로 모든 경로를 탐색하지 않아도 O(n×m) 시간에 최적값을 구할 수 있다.
정답을 외우기보다 글·표·그림 배치를 비교하며 내 답안을 보완하세요.
문제 4 예시답안 1
로그인 후 답안을 작성할 수 있습니다.