[BaekJoon/백준] 2579번 | 복습 1회 완료

 

처음에 짰던 방식

//arr[i][0]은 i 계단까지 밟는 최댓값. (0부터 시작)

#include <iostream>
#define MAX(a, b) ((a<=b)?b:a)
using namespace std;

int arr[300][2];
int N;
int f, s;

int main() {
    cin >> N;
    
    for(int i = 0; i < N; i++) {
        
        cin >> arr[i][0];
        
        
        
        if(i < 1) {
            arr[i][1]++; // 한칸 밟음.
        }
        else if(i < 2) {
            arr[i][0] = arr[i - 1][0] + arr[i][0]; // 2번쨰 칸을 밟은 최댓값은 결국 1 -> 2. ( 0 에서 2 가 아님!) -> X 이거 아니다.. 그냥 온거랑 한칸 띄워서 온거랑 구분해야할듯하다
            arr[i][1] = arr[i - 1][1] + 1; // 이전 칸에 한칸 더 밟음.
        }
        else {
            
            if (arr[i - 1][0] <= arr[i - 2][0] || arr[i - 1][1]>=2)// 이왕 같으면 두칸 떨어진 것 & 바로 이전 칸이 2번째 밟은 칸이라면 두칸 떨어진 것을 선택.
            {
                arr[i][0] = arr[i - 2][0] + arr[i][0];
                arr[i][1] = 1;
            }
            else {
                arr[i][0] = arr[i - 1][0] + arr[i][0];
                arr[i][1] = arr[i - 1][1] + 1;
            }
            
        }
    }
     cout << arr[N - 1][0];
}

 

의도는 맞았다. i에 관한 배열값은 해당 계단까지의 최대점수라는것.

 

하지만 배열 값 구성 과정에서 반례를 모두 캐치해내지 못했다.

테스트케이스는 통과했으나 제출 시 오답이 되어서, 한번 생각해봤더니 반례가 있었다.

 

계단이 3개고, 10 20 30 일 때 마지막 계단을 밟은 최댓값은 50인데

위의 내 풀이같은 경우엔 40을 뱉었다.

 

과정을 구성함에 있어서 빈틈이 있었다. 예를 들면 두 번째 계단인 20을 밟기 까지의 최댓값은 0(시작) + 20이 아니라

10 + 20인 30이 맞아서 배열 값에 30을 넣었으나, 세 번째 계단에서는 0 + 20으로 올라온 계단의 과정이 있었어야 했다. (이것이 최댓값)

 

다시 말하면, '해당 자리 - 1에서 올라온 값과, 해당 자리 - 2에서 올라온 값' 두 가지 경우가 필요했다.

 

그리고 계단을 연속 3번 밟을 수 없다는 전제와 함께, 이걸 더 자세히 풀면

 

계단 N까지의 최댓값 =

 

계단 N - 2 까지의 최댓값 + 계단 N

or

계단 N - 3 까지의 최댓값 + 계단 N - 1 + 계단 N

 

이라는 간단한 식이 나올 수 있었다.

 

이 식은 내 코드의 반례였던 '해당 자리 - 1에서 올라온 값과, 해당 자리 - 2에서 올라온 값' 두 경우를 구하는 동시에

두 번째 전 계단에서 왔는지 바로 이전 계단에서 왔는지 일일이 체크해나가며(연속 3번은 오를 수 없으므로) 2차원 배열을 사용할 필요도 없다.

 

내 기존 방법은

식이 간결한 대신에 코드가 원시적이였다면 (물론 정답도 아니였고)

위 방법은

식이 원시적인 대신에 코드가 간결했다.

 

내가 식을 간결하게 짜지 못하는 탓에, 이 점이 단점이라고 생각했기에

무조건 간결한 식을 구해야 한다고 추구했는데, 이 기회에 내가 꼭 단점만 갖고 있던 건 아니였다고 생각했다.

 

 

배열 맨 앞 0~3인덱스를 0으로 채워놓아서, 첫 계단을 인덱스 4부터 들어가게끔 구현했다. ( 첫번째 부터 세번째 계단까지는 식에서 out of bound index 오류가 날 수 있으므로, 식을 통일하기 위해 시작점을 앞으로 잡아준 것 뿐 )

//arr[i]는 각 계단 점수( 0 ~ 3 인덱스 까지는 0으로 채워놓음. 첫 계단은 인덱스 4부터 시작->4계단=1계단)
//score[i]는 i 계단까지 밟는 최댓값. (0 ~ 3 인덱스 까지는 0으로 채워놓음. 첫 계단은 인덱스 4부터 시작->4계단 = 1계단)

#include <iostream>
#define MAX(a, b) ((a<=b)?b:a)
using namespace std;

int arr[303]; // 앞의 3개를 0으로 채우고 인덱스 4부터 시작.
int score[303]; // 계산 배열
int N;
int f, s;

int main() {
    cin >> N;
    
    for(int i = 4; i < N + 4; i++) {
        
        cin >> arr[i];
        score[i] = arr[i];
        
        score[i] = MAX(score[i - 2] + arr[i], score[i - 3] + arr[i - 1] + arr[i]);
    }
    cout << score[N + 3];
}

 

배열을 통해 각 인덱스 자리의 요소값이 'i 번째 자리 까지의 경로/방법의 최댓값/최솟값' 유형의 문제를 연속해서 마주하고 있다.

 

 

 

참고

www.acmicpc.net/board/view/60699

n번째 계단은 반드시 포함
세 번 연속은 불가능

dp[n] = n번째 계단까지의 최대 점수

dp[n] = (n-2 계단까지의 최대 점수 + n번째 계단 점수 or n-3 계단까지의 최대 점수 + n-1번째 계단 점수 + n번째 계단 점수) 둘 중 더 큰 값

dp[n] = max(dp[n-2] + step[n], dp[n-3] + step[n-1] + step[n])

 

 

---

2021.02.24 복습

다시 풀어보았다.

#include <stdio.h>
#define MAX(a,b) ((a<=b)?b:a)

int dp[304];
int s[304]; // 0 ~ 303까지 둠으로써, 조건을 위한 3의 공간을 확보
int N;

int main() {
    
    scanf("%d", &N);
    
    for(int i = 3; i < N + 3; i++) {
        scanf("%d", &s[i]);
        
        dp[i] = MAX(dp[i - 3] + s[i - 1] + s[i], dp[i - 2] + s[i]);
    }
    
    printf("%d", dp[N + 2]);
}


/*
 
 dp[N] : N번째 계단까지 밝는 경우 최댓값. (해당 계단까지 점수 최댓값)
 매 순간이 3계단이 아닌 경우에서, 계단을 밟는 경우를 생각해냄.
 (참고로, 계단을 밟지 않는 경우가 필요한 문제유형이 아님)
 
 A. 한칸 뛰고 이전계단 밟고 현재계단 밟는경우
 : dp[i - 3] + s[i - 1] + s[i]
 
 B. 한칸 뛰고 현재계단 밟는경우
 : dp[i - 2] + s[i]
 
 
 */