[c++] 11052 붕어빵판매하기

https://www.acmicpc.net/problem/11052

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
int price[10001], memo[10001];
int P(int N) {
    
    if (N == 0return memo[N] = 0;
    if (N == 1return memo[N] = price[N];
    int k;
    for (k = 1; k <= N; k++)
    {
        if (memo[N] < P(N - k) + price[k])
        {
            memo[N] = P(N - k) + price[k];
        }
    }
    return memo[N];
}
 
int main() {
    int N = 0;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> price[i];
    }
    cout << P(N) << "\n";
 
 
    return 0;
}
cs
Dp문제이다.  Dp문제에서 제일 중요한 것은 점화식을 어떻게 짤것인가?를 고민하는 것이다.

먼저보자 문제는 총 N개의 붕어빵을 팔았을때 얻을 수 있는 최대값을 구하라는 것이다.

정의를 잘 내려야 점화식을 해결할때 큰 도움이 된다.
1. 이를 이용해 붕어빵값의 최대값을 구하는 함수를 P(N)이라고 하자.

P(N)에서 마지막에 올 수 있는 인자의 값은 무엇이 될까?? 모른다... 하지만 !! 어떤값이 올지는 몰라도 가정은 할 수 있다. 문제조건에서 주어진 Price(i)들중에 하나가 올 수있다는 것은 너무나 당연하다. 식으로 나타내면

2. 붕어빵의 최대값을 구하는 함수를  P(N) = ? + price(i) 라고 나타 낼 수 있다. 이렇게 식을 세우면 또하나의 힌트를 얻게된다. N개에서 i개를 판 가격이 price(i)이므로 ?의 개수는 N-i라고 나타낼 수 있다.

그렇다면 N-i개의 최대가격과 Price(i)가 합쳐지면 

앞서 말했듯이 문제를 구할 때 정의를 잘 내리면 점화식을 해결할 때 큰 도움이 된다고 했다. 
P(N) = N개에서의 최대값 이므로 N-i개에서의 최대값은 P(N-i)로 정의 할 수 있다. 

3.점화식 : P(N) = P(N-i) + price(i) 을 구할 수 있다.
위 코드로 점화식을 구현하였다. 

[c++] stack 개념과 예제

백준의 알고리즘 오프라인 강의를 들으면서 지금까지 배웠던 내용들을 간단하게 정리하려고 한다.스택 -한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저나오기 때문에 LIFO(Last In First Out)이라고 한다. 스택은 두가지 연산으로 이루어져있는데 -push함수 : 스택에 자료를 넣는 연산 -pop 함... » 내용보기

[c++]10799번 쇠막대기 / stack

https://www.acmicpc.net/problem/10799문제는 굉장히 어려워 보이나 규칙성을 찾는다면 스택을 이용해 간단하게 해결할 수 있는 문제이다.입력받은 string을 순차적으로 검사해괄호 ( 가 있다면 스택에 추가하고,괄호 ) 가 있다면 레이저에 의한 ')'인지 쇠막대기에 의한 ')'인지확인하여 각각의 경우를 처리해주면 된다.레이저에의... » 내용보기

[c++] 2579번 계단 오르기 / DP- topdown

이번 문제도 DP관련 문제이다. DP관련 문제가 나오는 경우엔 점화식을 세우는 것이 중요하다.이글을 쓰기 3일 전에 미리 풀어보았는데 왠지모르게 오류가나서 잠깐 미뤘다가 오늘 다시보았는데 술술 풀렸다.환기를 시키는 것이 중요하다는 것을 알았다. 사실상 점화식을 잘못세워서 시간을 낭비했는데 이런 곳에서 수학의 중요성을... 깨닫는다.흫그흑 머리가 좋아야해... » 내용보기

[c/ c++]1,2,3 더하기-2가지 방법

백준 알고리즘의 1,2,3 더하기 문제이다. dynamic을 이용하여 풀었다.이 문제를 풀땐 점화식을 세우고  그 점화식을 통해 문제를 해결해야한다.N이라는 숫자를 만들려면 N = ? + ? + ? + .... + ? + 1 로 만드는 방법 1. N = N-1 + 1N = ? + ? + ? + .... + ? + 2 로 만드는 방법 2... » 내용보기