[코드트리] 행복한 수열의 개수

 

 

---

 

문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

개념

구현, 격자 안에서 완전탐색 

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

#include <iostream>
using namespace std;

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

  int n, m;
  cin >> n >> m;
  int arr[100][100];

  // 격자 입력 받기
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> arr[i][j];
    }
  }

  int happy = 0;

  // 행 검사
  for (int i = 0; i < n; i++) {
    int cnt = 1;
    for (int j = 1; j < n; j++) { // j는 1부터
      if (arr[i][j] == arr[i][j - 1]) {
        cnt++;
      } else {
        cnt = 1;
      }
      if (cnt >= m) {
        happy++;
        break;  // 중복 검사 방지용 건너뛰기
      }
    }
  }

  // 열 검사
  for (int j = 0; j < n; j++) {
    int cnt = 1;
    for (int i = 1; i < n; i++) {
      if (arr[i][j] == arr[i - 1][j]) {
        cnt++;
      } else {
        cnt = 1;
      }
      if (cnt >= m) {
        happy++;
        break;
      }
    }
  }

  if (n == 1 && m ==1)
    cout << 2;
  else
      cout << happy;
  
  return 0;
}

 

 

 

 

코드 설명

행복한 수열은 연속하여 m개 이상의 동일한 원소가 나오는 순간이 존재하는 수열이다.

그리고 아래에서 행과 열마다 총 2*n개의 수열이라고 생각하라고 말하고 있다.

따라서 행복한 수열의 개수를 셀 때도, 행과 열을 나누어 생각해야 한다.

 

행 검사

for (int i = 0; i < n; i++) {
    int cnt = 1;
    for (int j = 1; j < n; j++) {
        if (arr[i][j] == arr[i][j - 1]) {
            cnt++;
        } else {
            cnt = 1;
        }
        if (cnt >= m) {
            happy++;
            break;
        }
    }
}

 

먼저 arr[0][0]을 기준으로 arr[0][1].. arr[0][n-1]까지 검사하면서

해당 행(가로줄)에서 연속된 숫자가 나올때마다 cnt를 증가시킨다.

만약 연속된 수가 나오지 않으면 바로 1로 바꾸면서 초기화한다.

m이상이면 행복한 수열이므로 행복한 수열의 개수인 happy를 증가시킨다.

 

 

열 검사

for (int j = 0; j < n; j++) {
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i][j] == arr[i - 1][j]) {
            cnt++;
        } else {
            cnt = 1;
        }
        if (cnt >= m) {
            happy++;
            break;
        }
    }
}

 

행 검사와 동일한 방식이지만 i를 이전 값과 비교할 때 상하로 움직이며 검사한다.

 

 

예외 처리 ⚠️

  if (n == 1 && m == 1)
    cout << 2;
  else
      cout << happy;

 

사실 이 부분 때문에 틀렸는데.. n과 m이 1인 경우

행으로 돌리나 열로 돌리나 똑같이 1씩 증가하여 happy가 2가 된다.

만약 테스트케이스가 없었다면 알아차리지 못할 예외였기 때문에 꼭 기억해두자.

 

 

---