[BOJ 백준] 10836번 여왕벌 서브태스크

문제

BOJ 10836 : https://www.acmicpc.net/problem/10836

10836번: 여왕벌

접근

 이 문제는 서브태스크 문제로 입력값 등의 제한에 따라 점수가 다르게 채점된다. 즉 제한이 까다로워질수록 문제를 좀 더 효율적으로 풀어야 한다는 뜻이다.

 문제를 잘 보면 i = 0, j = 0인 열과 행만 계산해주면 나머지 값은 따로 계산해 주지 않아도 된다. 이유는 다음과 같다.

 제일 첫 번째 열과 행의 애벌레가 성장하는 크기는 0, 1, 2로 순서대로 주어진다. 그리고 나머지 칸의 애벌레는 인접한 왼쪽 or 위의 애벌레가 성장하는 크기 중 더 크게 성장하는 애벌레를 따라 성장한다. 이 경우 무조건 왼쪽의 애벌레와 위쪽의 애벌레의 성장하는 크기가 같거나 위쪽의 애벌레가 더 크게 성장할 수밖에 없다. 왜냐하면 애벌레가 성장하는 크기는 0 ~ 2의 순서대로 주어지기 때문에 절대 그림에서 파란색 칸이 붉은색 칸보다 성장하는 크기가 클 수 없기 때문이다. 

따라서 결론적으로 애벌레들의 성장하는 크기는 이런 모양을 따르게 된다. 즉, 제일 왼쪽 열과 제일 위쪽 행의 애벌레들의 성장만 계산해주면 된다. 

코드

#include <iostream>

using namespace std;

int bee[700 * 700];

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    int m, n, a, b, c;
    cin >> m >> n;

    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        for (int j = a; j < a + b; j++) 
            bee[j]++;
        for (int j = a + b; j < a + b + c; j++)
            bee[j] += 2;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (j == 0)
                cout << bee[m - 1 - i] + 1 << " ";
            else
                cout << bee[m - 1 + j] + 1 << " ";
        }
        cout << "\n";
    }

    return 0;
}

// 서브태스크 83점

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    int m, n, t, bee[701][701];
    cin >> m >> n;

    for (int i = 0; i < n; i++) {
        int rx = m - 1, ry = 0;
        for (int c = 0; c < 3; c++) {
            cin >> t;
            for (int j = 0; j < t; j++) {
                bee[rx][ry] += c;
                if (rx > 0)
                    rx--;
                else
                    ry++;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0)
                bee[i][j] += 1;
            else
                bee[i][j] = bee[i - 1][j];
            cout << bee[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study