[BOJ] 1965번 상자넣기 (C++)

Alice·2023년 2월 3일
0
post-thumbnail

BOJ 1965번 <상자 넣기>
난이도 : 실버 2
알고리즘 분류 : DP


접근 방법

  1. 우선 DP 배열을 하나 생성한다.
    i 번째 원소까지 담을 수 있는 상자의 최대 갯수를 저장한다.
    여기서 초기값으로 dp[i] = 1 를 설정해줘야 한다. 자기 자신을 선택하는 순간 상자의 갯수는 최소 1개가 되기 때문이다.

  2. 상자 크기를 저장해둔 배열을 탐색한다. 다만 i 번째 상자에 담을 수 있는 상자를 탐색한다.
    그래야지 값 갱신에 유의미하기 때문이다.

  3. 1~ i-1 번째 상자들 중 i 번째 상자에 담을 수 있는 상자들이 담을 수 있는 최대 상자의 갯수
    (dp[1] ~ dp[i-1]) 와 비교하여 dp[i] 보다 큰 경우 dp[i] 의 값을 비교값 + 1 로 갱신한다.


코드

int N;
int map[1001];
int dp[1001];

void input() {

	for (int i = 1; i <= N; i++) {
		cin >> map[i];
	}

}

void solve() {

	int max = 0;
    
	for (int i = 1; i <= N; i++) {
		dp[i] = 1; 

		for (int j = 1; j < i; j++) { 
			if (map[j] < map[i]) { 
				if (dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		if (dp[i] > max) {
			max = dp[i];
		}

	}
	cout << max << endl;

}


int main() {
	cin >> N;
	input();
	solve();
}

고찰

어떤 의미로는 주어진 수열 중 가장 긴 증가하는 부분수열 을 구하는 문제이기도 하다.
패턴을 기억해두자.

profile
SSAFY 11th

0개의 댓글