1110: 징검다리

Link : judge.koreatech.ac.kr/problem.php?id=1110

---

1. 문제

• 광성이가 여자친구를 만나러 가기 위해서는 항상 징검다리를 건너야 합니다. 그 징검다리의 각각의 돌에는 숫자가 쓰여 있는데, 1부터 쓰인 숫자 중 원하는 만큼 앞으로 전진할 수 있습니다. 징검다리에 3이 씌어 있으면 1칸 혹은 2칸 혹은 3칸을 앞으로 갈 수 있습니다. 예를 들어 아래와 같이 징검다리가 있다면
  3, 2, 0, 5, 2, 1
  첫 번째, 네 번째를 밟고 다리를 건너갈 수 있습니다.
  다리에 쓰여진 숫자가 주어졌을 때, 광성이가 이 다리를 건너갈 수 있는지 판단하는 프로그램을 짜 주세요.

 

---

2. 문제의 조건

• 1 <= N <= 10,000

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 1만개의 데이터기 때문에 O(N^2)이내의 시간안에 풀면 된다고 생각하였습니다.

 

• 아이디어
  
  arr[pos] 현재의 자리를 기준으로 주어진 value 만큼 움직일 수 있습니다. [3, 4, 0, 0, 2, 4, 3, 2, 0, 1, 5] 일 경우 idx가 0일때 이는 idx 1, 2, 3을 갈 수 있습니다.
  idx 1은 5(4+1)칸의 이득이고 idx 2는 (0+2)의 이득, idx 3은 (0+3)의 이득인데 idx1이 제일 크므로 현재 pos는 idx 1이됩니다.
  idx가 높으면 높을 수록 + 되는 값이 많은 이유는 목적지에 i만큼 가까워지기 때문입니다. 이는 즉 i칸 만큼 덜 가도 된다는 의미입니다.
  
  총 arr[data] n일경우는 for의 시간복잡도가 O(N)으로 바로 탈출이고, arr[data]가 1일경우 for문이 O(1)이 된다고 생각하여 O(N)정도 걸린다고 생각하였습니다.

 

 

---

4. 풀이 방법

• 현재의 위치가 이미 도착지점이거나 현재의 위치에서 더 갈 수 있는 거리가 도착지점 이상이라면 while를 종료합니다.
• 1부터 현재 갈 수 있는 거리 만큼 for문을 반복합니다.
• 만약 arr[pos + i] 현재의 자리에서 갈 수 있는 거리 + 가까워진 거리가 최대 값이라면, 갱싱하고 그 위치를 기억해줍니다.
• 만약 최대값이 0이라면 더 이상 갈 수 없는 뜻이므로 No를 외쳐줍니다.
• 갈 수 있다면 현재의 위치 pos를 갱신합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/61

 

---

 

cjw.git@gmail.com