[백준/BOJ] 6988 타일 밟기★- 접근과 풀이 (c++)

https://www.acmicpc.net/problem/6988

6988번: 타일 밟기

목에 칼이들어와도 하루 한문제 백준풀기를 실천하자.

장르는 내가 젤 좋아하는(풀면 기분좋은) dp문제.

정올문제는 언제나 어렵다.. 초등학생들이 이걸 푼다고?..

---

접근 방법

 

숫자가 3000개 뿐이고, 두 숫자의 관계를 이용하여 2차원 dp로 풀면 어떻게든 풀릴 것 같다는 감이 왔다.

 

두 개의 숫자를 짝을지어주면, 숫자의 차이와 시작 지점을 지정할 수 있다.

num1과 num2를 고르면, 숫자의 차이(@)는 num2 - num1이 되고, num1 부터 num1, num1+@, num1+@+@ ... 순으로 이어진다. 

 

그래서 " dp[num][diff] = num부터 시작하여 공차가 diff인 수열의 합 "  으로 풀려고 하였으나 숫자의 최댓값이 100만이다. 주어진 숫자는 오름차순이므로 유일성이 존재하니까, 숫자의 index를 이용했다.

100만개의 배열 크기는 MLE에 문제가 없고, 해시를 적절히 사용하여

 " dp[idx1][idx2] = " arr[idx1] 에서 arr[idx2]로 배열의 끝까지 이어지는 수열의 합"

으로 정의하였다.

 

그리고 코너케이스인 997001 ~ 1000000 의 합은 int범위를 살짝 넘기므로 자료형에 주의하자. 제출 전에 눈치채서 기분이 좋았는데, 타일을 3개 이상 밟지 못하면 0을 출력하는 조건을 못봐서 95퍼에서 자꾸 틀렸다 ㅋㅋ

 

그리고 모든 int형을 long long 자료형으로 바꿔주는 꼼수(?)를 보기만 하다 처음 써봤는데, 상당히 좋다.

방법은 define 문을사용하고 main함수의 자료형만 바꿔주면 된다.

#define int long long
signed main() { ... }

 

---

풀이

 

tag : dp

 

#include<iostream>
#include<string.h>
#define int long long
using namespace std;
int N;
int arr[3001];
int isNumHasIndex[4000001];
int dp[5000][5000];
int maxConseq = 2;
int solve(int idx1,int idx2,int conseq){
  //idx1번에서 idx2번으로 뛸대 최대
  int nextNum = arr[idx2] + arr[idx2] - arr[idx1];
  int nextIdx = isNumHasIndex[nextNum];
  maxConseq = max(conseq, maxConseq); //연속된 타일 밟는 횟수 확인
  if(isNumHasIndex[nextNum]==-1) //다음에 해당하는 수 없음
    return 0;
  int &ret = dp[idx1][idx2];
  if(ret!=-1)
    return ret;
  ret =  solve(idx2,nextIdx,conseq+1)+nextNum;
  return ret;
}
signed main(){
  memset(isNumHasIndex,-1,sizeof(isNumHasIndex)); //0번인덱스조심
  memset(dp, -1, sizeof(dp));
  cin >> N;
  for (int i = 0; i < N;i++){
    cin >> arr[i];
    isNumHasIndex[arr[i]] = i;
  }
  int ans = 0;
  for (int i = 0; i < N;i++){
    for (int j = i+1; j < N;j++){
      ans=max(ans,solve(i,j,2)+arr[j]+arr[i]);
    }
  }
  if(maxConseq==2)
    ans = 0;
  cout << ans;
}