[Codility] NumberSolitaire c++

• 문제

N개의 연속된 정사각형으로 구성된 보드에서 게임이 진행된다.

0번 정사각형의 조약돌을 N-1 정사각형으로 이동시켜야 하는 게임이다.

각 차례마다, 주사위를 던지고 주사위 윗면의 숫자 K를 고려한다. 

그런 다음 현재 I에 서 있는 조약돌을  I + K로 이동시킨다.

 I + K가 존재하지 않으면 유효한 인덱스를 얻을 때까지 주사위를 다시 던진다.

게임이 끝난 후(조약돌이 N-1 로 이동했을 때), 이동한 모든 사각형에 쓰여진 숫자의 합을 구한다. 

 

결론, A[0] → A[N-1] 로 이동할 때의 배열 원소의 최대 합을 구하는 문제이다.

 

 

문제 해결

int solution(vector<int> &A) { 
    vector<int> temp(A.size(), -1);
    temp[0] =  A[0];
    for(unsigned int i = 1;i< A.size();i++)
    {
        int j =  i<6? 0: (i- 6);
       auto itr = std::max_element(temp.begin() + j, temp.begin() + i);
       temp[i] = (*itr +  A[i]);
        
    }
    return temp[A.size() - 1];
}

 

예제 )

위의 코드로 아래와 같은 식이 나온다.

vector<int> A = { 1, -2, 0, 9, -1, 2 } 일 때

j	i	iter	A[i]	*iter + A[i]
0	1	1	-2	-1
0	2	1	0	1
0	3	1	9	10
0	4	10	-1	9
0	5	10	2	12

 

A 벡터의 0번 부터 1 ~ 5번을 차례로 비교한다.

1회차 : temp[1] = A[0] ~ A[1] 중 가장 큰 원소 + A[1]

2회차 : temp[2] = A[0] ~ A[2] 중 가장 큰 원소 + A[2]

3회차 : temp[3] = A[0] ~ A[3] 중 가장 큰 원소 + A[3]

4회차 : temp[4] = A[0] ~ A[4] 중 가장 큰 원소 + A[4]

5회차 : temp[5] = A[0] ~ A[5] 중 가장 큰 원소 + A[5]

 

temp의 마지막 원소가 이동할 때의 최댓값이 저장되어 있다.