[알고리즘 문제풀이] 기타 코딩테스트 1-4

 

문제 : 

N개의 발판이 주어지고, 각 발판에는 양의 정수 혹은 음의 정수가 적혀있다. 특정 발판을 밟을 경우, 해당 발판에 적혀있는 숫자만큼 좌로 혹은 우로 이동하게 된다. 음수가 적혀 있을 때는 왼쪽으로, 양수가 적혀 있을 때는 오른쪽으로 이동한다. 

 

A씨가 5번째 발판에 있으면 발판의 값이 4이므로 오른쪽으로 4칸 이동한다. 만약 A씨가 4번째 발판에 있으면, 발판의 값이 -2이므로 왼쪽으로 2칸 이동한다.

A씨는 1번째, 2번째, 3번째 발판에서 발판을 밟기 시작할 수 있다. 그렇게 발판을 하나하나 밟아 나가다가, 이미 밟았던 발판을 다시 밟을 경우 발판 밟기를 종료한다.  예를 들어, A씨가 1번째 발판에서 발판 밟기를 시작할 경우 아래와 같이 발판을 밟아 나간다.

 

발판의 개수와 각각의 발판에 적혀있는 숫자를 입력받고, A씨가 1번째, 2번째, 3번째 발판에서 발판 밟기를 시작할 수 있다고 할 때 A씨가 밟을 수 있는 발판 개수의 최댓값을 출력하시오.

 

 

 

입력 :

입력의 첫 번째 줄에 발판의 개수 정수 N을 입력받는다.

3 ≦ N ≦ 100

두 번째 줄에는 N개의 숫자에 대하여 1번째 발판부터 순서대로 발판에 적혀있는 숫자를 공백을 구분자로 입력받는다. 이 숫자는 양의 정수이거나 음의 정수이다.

A씨가 발판을 밟아 나가다가 발판의 범위를 벗어나는 경우는 고려하지 않는다.

 

ex)

10
3 5 -1 -2 4 4 3 -2 -3 -2

 

 

 

출력 :

A씨가 1번째, 2번째, 3번째 발판에서 발판 밟기를 시작할 수 있다고 할 때 A씨가 밟을 수 있는 발판 개수의 최댓값을 출력한다.

ex)

8

 

 

 

풀이 및 코드 :

단순 구현으로 풀이해주자. 복잡하지 않은 문제이다.

 

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int N;
vector <int> v;
int MAX = 0;
int visited[101] = { 0, };

void solution() {
	int iter = 0;
	int nowmax = 0;
	while (iter != 3) { //0,1,2까지만 반복하겠다.
		int pointer = iter;
		while (visited[pointer]==0&&pointer>=0&&pointer<v.size()) { //방문하지 않은곳에만 방문한다.
			visited[pointer] = 1;//방문체크해준다.
			pointer += v[pointer];
			nowmax++;
		}
		nowmax++; //마지막 밟은 발판도 더해준다.
		iter++;
		//초기화
		memset(visited, 0, sizeof(visited));//방문배열을 초기화한다.
		if (MAX <= nowmax)
			MAX = nowmax;
		nowmax = 0;
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int t;
		cin >> t;
		v.push_back(t);
	}
	solution();
	cout << MAX << endl;
}