평범한 개발 일지

간단한 그리디 문제입니다.

처음에는 한 곳의 브랜드를 선택하면 그 곳만 선택해야 하는지 알았지만 질문들을 찾아보니 다른 브랜드끼리 선택해도 되는 거였습니다.

따라서 3가지 경우를 생각하면 됩니다.

1. 묶음으로 다 사기
2. 묶으로 살 수 있는 만큼 사고 단품으로 사기
3. 단품으로 다 사기

따라서,

- 묶음으로 살 경우의 최솟값(Sum_min)

- 단품으로 살 경우의 최솟값(piece_min)

에 대한 변수를 선언하고 이것을 토대로 계산을 진행하면 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int n, m;
int sum_min = ~(1 << 31);
int piece_min = ~(1 << 31);
int min = ~(1 << 31);

void input() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a == 0 || b == 0) { // 0이 나오면 최솟값은 0이되고 다 구해지게 됩니다.
			sum_min = 0;
			piece_min = 0;
			break;
		}
		sum_min = sum_min > a ? a : sum_min; // 묶음 최소값
		piece_min = piece_min > b ? b : piece_min; // 단품 최소값
	}
}

void solve() {
	if (sum_min == 0 || piece_min == 0) {
		printf("0");
		return;
	}
	int remain = n % 6;
	int a = (n / 6+1) * (sum_min); // 1번 경우
	int b = n / 6 * sum_min + remain * piece_min; // 2번 경우
	int c = n * piece_min; // 3번 경우
	min = min > a ? a : min;
	min = min > b ? b : min;
	min = min > c ? c : min;
	printf("%d", min);
}

int main(void) {
	input();
	solve();
} 

문제

본 문제는 그냥 보자마자 번뜩 아이디어가 떠올랐다. 문제
내 생각은 현재를 기준으로 전의 값들을 비교하면 된다고 생각이 들었다. 즉, 다이나믹 프로그래밍 문제이다.
즉, 현재 값 > 전의 값 & 지금까지의 길이 < 전의 값까지의 길이 이다.
처음에는 이 문제가 가장 큰 증가하는 부분 수열인줄 알고 그렇게 풀었다가 거기서 변수만 조금 수정하면 되서 그렇게 성공했다. 다이나믹 프로그래밍같은 문제는 차근차근 생각하고 어떤 변수를 저장하고 사용할지를 생각하면 될 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define SIZE 1001
using namespace std;

int n;
int dp[2][SIZE] = { 0 };

void input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &dp[0][i]);
}

void solve() {
    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        int num = dp[0][i];
        for (int j = 1; j < i; j++) {
            if (dp[0][j] < num && dp[1][j] > dp[1][i] ) {
                dp[1][i] = dp[1][j];
            }
        }
        dp[1][i]++;
    }

}

void print() {
    int max = dp[1][1];
    for (int i = 2; i <= n; i++)
        if (dp[1][i] > max)
            max = dp[1][i];
    printf("%d", max);
}

int main(void) {
    input();
    solve();
    print();
}

본 문제는 간단한 DP문제이다. 특히, 점화식이 존재하기 때문에 더 쉽다. 문제
나 같은 경우에는 처음에 dp가 아닌 그냥 때려 박았는데... 컴파일 에러가 발생했다. 그 이유는 1000!가 long long 을 사용하더라도 한참 벗어나는 어마 무시하게 큰 값이기 때문이다.
따라서 여기서는 파스칼의 삼각형을 사용해서 풀어야 한다.즉, 간단하게 설명하면
nCk = n-1Ck + n-1Ck-1 이다.

전체적인 코드는 밑과 같다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define SIZE 1001
using namespace std;

int n, k;
int dp[SIZE][SIZE] = { 0 };

void input() {
    scanf("%d %d", &n, &k);
}

void solve() {
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i < SIZE; i++) {
        dp[i][0] = 1;
        for (int j = 1; j < i; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;
        dp[i][i] = 1;
    }
}

void print() {
    printf("%d", dp[n][k]);
}
int main(void) {
    input();
    solve();
    print();
}