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

문제

• https://www.codetree.ai/missions/2/problems/number-of-happy-sequence?utm_source=clipboard&utm_medium=text

해결방법

• 우선 n * n개의 배열을 만듦
• n과 m의 최솟값은 1이고, 최댓값이 100이므로, O(n^2)의 완전탐색이 가능할 것으로 판단
• 우선 직전 값을 담는 mem변수를 활용하여, 직전 값과 현재 수열의 값을 비교하는 방식으로 전개
• 여기서 m은 1이 될 수 있으므로, m이 1이 될 경우, 답은 2n개가 나온다는 것을 명심해야 한다.

코드

#include <iostream>

#define MAX_N 100
#define MAX_M 100

using namespace std;

int arr[MAX_N][MAX_N];
int n, m;

int main() {

    cin >> n >> m;

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

    int result = 0;

    // 우선 가로로 행복한 n개의 수열 탐색과정
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        int mem;
        for(int j = 0; j < n; j++) {
            // 우선 첫 번째 수라면, 연속 cnt를 새야 하므로 cnt
            if (j == 0) {
                mem = arr[i][j];
            }
            else {
                // 이전 값과 일치할 때(즉, 연속할 때)
                if (mem == arr[i][j]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                    mem = arr[i][j];
                }
                // 혹시라도 cnt가 m과 일치하다면

            }
            if (cnt == m) {
                result++;
                break;
            }
        }
    }
	
    // 세로로 행복한 n개의 행복한 수열 탐색
    for(int j = 0; j < n; j++) {
        int cnt = 1;
        int mem;
        for(int i = 0; i < n; i++) {
            // 우선 첫 번째 수라면, 연속 cnt를 새야 하므로 cnt
            if (i == 0) {
                mem = arr[i][j];
            }
            else {
                // 이전 값과 일치할 때(즉, 연속할 때)
                if (mem == arr[i][j]) {
                    cnt++;
                }
                else {
                    cnt = 1;
                    mem = arr[i][j];
                }
                // 혹시라도 cnt가 m과 일치하다면

            }
            if (cnt == m) {
                result++;
                break;
            }
        }
    }
    cout << result;
    return 0;
}

개선 방향

• 직전 값을 저장하는 mem변수를 활용하였지만, 그럴 필요 없이 arr[i][j] == arr[i][j]와 같이 n-1번 반복하는 코드를 짜서 더 간결하게 풀 수 있겠다.
• 추가적으로 반복되는 부분(for loop)을 함수를 사용해서 풀 수도 있겠다