BEEZI life

이 문제는 어렵지 않은 하드코딩 문제이지만, 디버깅을 하는 과정에서 항상 놓치고 있던 것을 머릿속에 각인시키고자 글을 쓴다.

전략

내가 문제에 사용한 전략은 아래와 같다.

1. 모든 원소마다 19개의 테트로미노의 최댓값을 비교한다.

2. 테트로미노의 시작점은 최대한 좌측 상단에 있는 정사각형이다.

3. 시작점으로부터 가장 왼쪽에 있는 정사각형과의 거리에 따라서 type을 정한다.

    ->가장 왼쪽에 있는 사각형의 index가 0보다 작지 않게 하기 위해서

4. 모든 원소에 초깃값으로 매우 큰 음수값을 넣어서 경계를 신경 쓰지 않도록 한다.

이러한 전략을 적용한 테트로미노 19개의 모양은 아래와 같다.

위와 같은 전략을 사용하여 코딩을 했을 때, 대부분의 경우는 옳은 답이 나온다.

디버깅

하지만, 4번의 전략으로 오른쪽, 아래쪽 경계를 신경쓰지 않았기 때문에
주어진 배열의 크기인 n,m이 최대치인 500일 경우, 경계를 넘는 값을 참조하여 틀린 값들이 나왔다.

예를 들어, 아래와 같은 배열이 주어졌을 때

경곗값을 검사하지 않았기 때문에, 테트로미노가 아래와 같이 위치하는 경우도 생겼다.

이러한 경우들을 방지하기 위해서 처음에 잡아놓는 배열의 크기를 503(최대로 참조할 수 있는 범위) 로 늘렸고,

503의 index까지 초깃값을 -4000으로 세팅해주었다.

코드

#include <bits/stdc++.h>
#define MAX 500

using namespace std;
int a[MAX+2][MAX+2];

int type0(int i, int j){
  // 해당 행/열 반대방향으로 블럭이 없는경우
  int maxCount=0;
  int cnt;
  
  //1
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //2
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i][j+3];
  if(maxCount<cnt) maxCount=cnt;

  //3
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+3][j];
  if(maxCount<cnt) maxCount=cnt;

  //4
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //5
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j];
  if(maxCount<cnt) maxCount=cnt;

  //6
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;

  //9
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //10
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //11
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //12
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j+1];
  if(maxCount<cnt) maxCount=cnt;
  
  //15
  cnt = a[i][j]+a[i][j+1]+a[i+1][j+1]+a[i+1][j+2];
  if(maxCount<cnt) maxCount=cnt;

  //16
  cnt = a[i][j]+a[i][j+1]+a[i][j+2]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;
   
  //19
  cnt = a[i][j]+a[i+1][j]+a[i+1][j+1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type1(int i, int j){
  int maxCount=0;
  int cnt;
  //8
  cnt = a[i][j]+a[i+1][j]+a[i+2][j]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //13
  cnt = a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //14
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j-1];
  if(maxCount<cnt) maxCount=cnt;

  //17
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+2][j];
  if(maxCount<cnt) maxCount=cnt;

  //18
  cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j+1];
  if(maxCount<cnt) maxCount=cnt;

  return maxCount;
}

int type2(int i, int j){
  int cnt = a[i][j]+a[i+1][j]+a[i+1][j-1]+a[i+1][j-2];
  return cnt;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  for(int i=0; i<=MAX+2; i++){
    for(int j=0; j<=MAX+2; j++){
      // 최솟값을 미리 넣어놓기
      a[i][j]=-5000;
    }
  }

  int n, m;
  cin>>n>>m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>a[i][j];
    }
  }

  int maxCount=0;
  int cnt;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cnt=type0(i,j);
      if(maxCount<cnt) maxCount=cnt;

      if(j-1>=0){
        cnt=type1(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }

      if(j-2>=0){
        cnt=type2(i,j);
        if(maxCount<cnt) maxCount=cnt;
      }
    }
  }
  cout<<maxCount;
  return 0;
}

100솔, 골드5 달성기념!

이 문제의 조건은 두 가지이다.
① 이웃한 집과의 색은 달라야 한다.
② 첫 번째 집과 마지막 집의 색은 달라야 한다.

예시를 이용해 살펴보기

첫 번째 조건은 전형적인 DP로 해결할 수 있지만, 두 번째 조건은 조금 다른 방식으로 체크해줘야 한다.

문제의 예시에서

① 번 조건만 생각해 봤을 때에는,

D[i][j] : i번째 집을 j색으로 칠한다고 했을 때 비용의 최솟값,
a[i][j] : i번째 집을 j색으로 칠했을 때의 비용일 때

점화식은 D[i][j]=min(D[i-1][(j+1)%3], D[i-1][(j+2)%3]) + a[i][j] 이다.
여기에서 (j+1)%3, (j+2)%3의 표현은 j와는 다른 색을 선택한다는 의미이다.

이렇게 구한 D[n][0], D[n][1], D[n][2]값들의 최솟값이 답이 된다.

즉, n번째에 칠한 색(j)에 따른 비용의 최솟값(D[n][j])들을 비교하여 그중 가장 작은 비용이 답이 된다.

위의 예시에서는 D[n][0]=96, D[n][1]=172, D[n][2]=185가 되어,

D[n][0]이 답이 된다. 즉, 마지막 n번째 집에 빨간색을 칠했을 경우의 비용의 최솟값이 다른 색을 칠했을 경우와 비교해 가장 작다는 뜻이다.

문제풀이의 Key

여기에서 ②번의 조건을 추가한다면, 첫 번째 선택한 색과 마지막의 선택한 색을 비교해서 같으면 선택하지 못하게 해야 한다.

우리가 구하는 정답은 비용의 최솟값이다.

첫 번째 색이 k라고 하고, D [n][k](n번째 집에 k색을 칠할 때 비용의 최솟값)에 매우 큰 값을 넣는다면

마지막에 저절로 답에서 제외될 것이다.

위의 방법이 이 풀이의 핵심이다.

해결

첫 번째에 선택한 색을 k라고 두고, 

위에 서술해놓은 이 풀이의 핵심 key를 사용하여

첫 번째 집에 k가 아닌 색의 비용을 1000*1000이라 하고,

마지막 집에 k인 색의 비용을 1000*1000이라고 한다.

위와 같은 방법으로 k=0~2까지 순회하면서 k값에 따른 문제의 최솟값을 구한 뒤,

모든 최솟값을 비교해 그중 가장 작은 비용을 선택하면 해결된다.

코드

#include <bits/stdc++.h>
#define MAX 1000

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  int a[MAX+1][3]={0,}, d[MAX+1][3]={0,};
  cin>>n;
  for(int i=1; i<=n; i++){
    for(int j=0; j<3; j++){
      cin>>a[i][j];
    }
  }
  int res=1000*1000;
  for(int k=0; k<3; k++){
    // 첫번째집을 k로 선택하는 경우
    //cout<<k<<'\n';
    for(int i=1; i<=n; i++){
      for(int j=0; j<3; j++){
        d[i][j]=min(d[i-1][(j+1)%3],d[i-1][(j+2)%3])+a[i][j];
        if(i==1){
          d[i][j] = 1000*1000;
          if(j==k) d[i][j]=a[i][j];
        }else if(i==n && j==k){
          d[i][j] = 1000*1000;
        }
        //cout<<d[i][j]<<' ';
      }
      //cout<<'\n';
    }
    for(int j=0; j<3; j++){
      res=min(res, d[n][j]);
    }
  }
  cout<<res;
  return 0;
}

먼저 타일을 채울 수 있는 단위타일을 만들어 보면 아래와 같다

2*3의 타일은 3개지만, 2n * 3의 타일들은 2개씩 나온다. (1<n)

일단 4*3의 타일을 채우는 경우를 생각해보자

위와 같이 2*3단위타일이 2개 오거나, 4*3단위 타일이 1개 올 수 있다.

D[i]를 가로의 길이가 i인타일을 채우는 경우의 수라고 하면,

2*3단위 타일이 2개인 경우는 다르게 표현하면, D[2]에 2*3단위 타일이 연속해서 오는 경우이다 (곱사건)

4*3타일이 1개인 경우는 다르게 표현하면, 가로의 길이가 0인 타일을 채운 경우인 D[0]에 4*3단위 타일이 연속해서 오는 경우이다 (곱사건)

2*3단위 타일을 만드는 경우의 수는 3가지, 4*3단위 타일을 만드는 경우는 2가지이므로

 D[4] = D[2]*3 + D[0]*2

단, 여기에서 D[0]은 0*3의 타일에 아무것도 채우지 않는 경우의 수 이므로 D[0]=1이다.

조금 더 확장해서 6*3의 타일을 만드는 경우를 생각해보자.

이번에는 위의 예시에서 학습한 내용을 바로 적용해보았다.

2*3단위 타일을 만드는 경우의 수는 3가지, 2n * 3단위 타일을 만드는 경우는 2가지 (단, 1<n)이므로,

D[6] = D[4]*3 + D[2]*2 + D[0]*2

위의 예시들을 바탕으로 점화식을 세워보면

D[n] = D[n-2] * 3 + ∑D[n-2k] * 2 ( 단, 2<2k<=n, n은 2<n인 짝수 ), D[2]=3, D[0]=1

D[n] = 0 ( n은 홀수 )

#include <bits/stdc++.h>
#define MAX 30

using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin>>n;
  int d[MAX+1]={0,};
  d[0]=1;
  for(int i=1; i<=n; i++){
    if(i%2==0){
      if(i>=2) d[i]+=d[i-2]*3;
      if(i>=4){
        for(int j=4; j<=i; j+=2){
          d[i]+=d[i-j]*2; 
        }
      }
    }
  }
  cout<<d[n];
}

선언과 동시에 초기화 ( 0 만 가능 )

오늘 백준 11053번 가장 긴 증가하는 부분수열4를 해결할 때, 배열 초기화를 잘못하는 실수를 했다.

앞서 l[1001]배열을 {-1,-1,-1,...,-1}로 초기화 하려고 시도했다.

int a[1001], d[1001], l[1001]={-1,}

하지만 디버깅을 하며 살펴보니 왼쪽과 같이 {-1, 0, 0, ... 0} 으로 초기화가 되어있었다.

왜그런가 찾아보니, c++에서 {n, } 형태로 배열을 초기화 할 때는 n==0인 경우에만 가능하다는 것이였다.

추가) 2차원배열도 똑같은 방법으로 초기화 할 수 있다.

int d[201][201]={0,}

Memset함수 ( 0, -1 만 가능)

-1로 초기화 하기 위해서는

memset(l,-1,sizeof(l));

이렇게 memset을 활용해서 초기화 해야하고, memset함수도 주의해야 할 점이 있는데

초기화할 수 있는 값은 0과 -1만 가능하다는 것이다.

For문 ( 모든 경우 )

그 외의 숫자로 초기화 하기 위해서는 마음 편하게 for문으로 초기화 하는게 나을 것 같다.

for(int i=0; i<n; i++){
	l[i]=3;
}

비교함수 내부

반복문 내부분석 및 풀이

이 문제를 해결하기 위한 키는 src1의 인덱스의 범위가 char자료형의 범위라는것을 파악하는것이라고 생각한다.

관련링크

비교함수 내부

반복문 내부

이 문제의 핵심은 한 단어를 알아내는 것이다.

그렇게 하지 못하면 브루트포스를 사용하는 방법밖에 없다.

그 핵심의 한 단어를 알아내는 방법을

아래에 설명해놓았다.

반복문이 어떻게 돌아가는지 직접 손으로 작성해본 결과

핵심적인 열쇠를 알아낼 수 있었다.

관련 링크

비교함수 내부

풀이

이번 문제도 3번문제와 마찬가지로 12번라인에서 src가 있는 메모리주소를 알려주었고,

우리가 입력한 str값을 알맞게 변형하여 src값과 일치시키는 문제이다.

sar 연산자는 arithmetic한 shift right이므로 bit shift를 사용할 수 도 있지만,

정말 arithmetic하게 *16(2^4)를 해주는 방법도 있다는것을 알게 되었다.

리버싱공부 3일차 완료!

관련 링크