[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
[5. 배열] 단원의 기본 셋팅은 다음과 같다.
Q 5.4 배열에서 이동하기
주어진 위치 정보를 차례대로 걸어 나가는 보드게임이 있다고 하자.
각 위치에서 음이 아닌 정수값이 들어 있고, 해당 위치에서 최대 그 숫자만큼 앞으로 나아갈 수 있을때, 마지막 위치에 도달하도록 하자.
이 게임의 목표는 첫 번째 위치에서 시작해서 마지막 위치에 도달하는 것이다.
ex) A=<3,3,1,0,2,0,1> 의 i번째 위치에서는 최대 A[i]만큼 앞으로 나아갈 수 있다.
A[0] 은 3까지 움직일 수 있으므로 1만큼 움직인다.
A[1] 은 3까지 움직일 수 있으므로 3만큼 움직인다.
A[4] 는 2까지 움직일 수 있으므로 2만큼 움직인다.
A[6] 에 도달한다. << 승리.
B = <3,2,0,0,2,0,1>
B[0] 은 3까지 움직일 수 있으므로 1만큼 움직인다.
B[1] 은 2까지 움직일 수 있으나 어디로가도 0이되어 B[6]에 도달할 수 없다. 따라서 패배
위와 같이 해당 vector가 승리가 가능한지를 판단하는 게임을 만들자.
현재 위치에서 최대한 멀리 나아가는 것이 중요하므로 가장 멀리 나아갔던 경우와 i위치에서의 i+A[i] 값을 비교하여 큰 값이 마지막 위치에 다다를 수 있는지를 판단하는게 중요하다.
해당 코드와 결과는 다음과 같다.
'C++ 학습 > C++ 코딩인터뷰[5장]' 카테고리의 다른 글
| [5. 배열] 5.6 주식 한 번 사고팔기 (0) | 2025.01.14 |
|---|---|
| [5. 배열] 5.5 정렬된 배열에서 중복 제거하기 (0) | 2025.01.14 |
| [5. 배열] 5.3 임의의 두 정수값 곱하기 (0) | 2025.01.14 |
| [5. 배열] 5.2 임의의 정수값 증가시키기 (0) | 2025.01.14 |
| [5. 배열] 5.1 네덜란드 국기 문제 (0) | 2025.01.14 |
