전광판 줄 바꾸기 최대 점수
자바스크립트 코딩테스트 문제로 two-state-dp 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
두 줄짜리 전광판에서 매 위치마다 한 줄의 점수를 고르되, 줄을 바꿀 때 드는 비용을 고려해 얻을 수 있는 최대 점수를 구하세요.
문제 설명
길이가 같은 두 정수 배열 topScores, bottomScores와 정수 switchCost가 주어집니다.
전광판은 왼쪽부터 오른쪽으로 0번 위치부터 n - 1번 위치까지 이어져 있습니다. 각 위치에서는 위쪽 줄의 점수 topScores[i] 또는 아래쪽 줄의 점수 bottomScores[i] 중 하나를 반드시 선택해야 합니다.
이전 위치에서 선택한 줄과 현재 위치에서 선택한 줄이 다르면 switchCost만큼 점수가 차감됩니다. 첫 위치에서는 위쪽 줄이나 아래쪽 줄 어디서 시작해도 줄 변경 비용이 들지 않습니다.
전체 위치를 모두 지나며 얻을 수 있는 최대 점수를 반환하는 maxScoreWithSwitchingLines 함수를 작성하세요.
제한사항
topScores.length === bottomScores.length1 <= topScores.length <= 100000-10000 <= topScores[i], bottomScores[i] <= 100000 <= switchCost <= 10000- 매 위치에서는 반드시 위쪽 또는 아래쪽 중 하나를 선택해야 합니다.
- 반환값은 가능한 최대 총점입니다.
예시
- 입력:
topScores = [5, 1, 9, 1],bottomScores = [1, 8, 1, 8],switchCost = 3-> 출력:21 - 입력:
topScores = [4, 4, 4],bottomScores = [1, 10, 1],switchCost = 10-> 출력:12 - 입력:
topScores = [-5, -1, -5],bottomScores = [-2, -10, -2],switchCost = 1-> 출력:-7 - 입력:
topScores = [1, 100, 1],bottomScores = [50, 1, 50],switchCost = 0-> 출력:200
힌트
- 각 위치에서 “위쪽 줄로 끝나는 최고 점수”와 “아래쪽 줄로 끝나는 최고 점수”만 알면 다음 위치를 계산할 수 있습니다.
- 같은 줄을 유지하면 비용이 없고, 반대 줄에서 넘어오면
switchCost를 빼야 합니다. - 점수가 음수일 수 있으므로 단순히 점수가 양수인 칸만 고르는 방식은 사용할 수 없습니다.
해설
이 문제는 모든 선택 경로를 직접 만들면 경우의 수가 2^n으로 커집니다. 하지만 다음 위치를 계산할 때 필요한 정보는 아주 작습니다.
topDp를 현재 위치에서 위쪽 줄을 선택하고 끝났을 때의 최고 점수, bottomDp를 현재 위치에서 아래쪽 줄을 선택하고 끝났을 때의 최고 점수라고 합시다.
첫 위치에서는 줄을 바꾼 적이 없으므로 다음과 같이 시작합니다.
topDp = topScores[0]
bottomDp = bottomScores[0]
그다음 위치 i에서는 위쪽 줄로 끝나는 경우와 아래쪽 줄로 끝나는 경우를 각각 계산합니다.
- 위쪽 줄 선택: 이전에도 위쪽 줄이었거나, 아래쪽 줄에서 위쪽 줄로 바꿉니다.
- 아래쪽 줄 선택: 이전에도 아래쪽 줄이었거나, 위쪽 줄에서 아래쪽 줄로 바꿉니다.
따라서 점화식은 다음과 같습니다.
nextTop = Math.max(topDp, bottomDp - switchCost) + topScores[i]
nextBottom = Math.max(bottomDp, topDp - switchCost) + bottomScores[i]
계산 후 topDp, bottomDp를 새 값으로 바꾸며 끝까지 진행합니다. 마지막에는 어느 줄에서 끝나도 되므로 Math.max(topDp, bottomDp)를 반환합니다.
각 위치를 한 번씩만 확인하므로 시간 복잡도는 O(n)이고, 두 상태만 유지하므로 공간 복잡도는 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.