대엉코딩

www.acmicpc.net/problem/16637

1.풀이방법

- 수식과 정수를 나누는 작업을 따로 하지는 않았고 모두 index를 통해서 접근하였습니다.

- 모든 경우의 수를 재귀를 통해서 구현한 후 연산하시면 됩니다.

- 처음에 문제조건을 파악하고 무조건 dp라고 생각하고 반복문을 이용해서 바텀업 방식으로 구현을 했는데

- 계속 틀렸다고 나와서 방식을 약간 바꿨는데......하 아직도 첫 소스에서는 어떤 사항을 잡지 못하는지

- 모르겠네요...... 역시 테스트케이스는 되는데 제출하면 틀릴 때는 참 예외사항 발견하기가 어렵네요

- 두번째로 틀린 소스도 올릴테니 지적과 조언좀 부탁드려요...(뭐가 잘못 되었을 까요......ㅠ)

2. 주의사항

- 어이가 없지만.......1일 경우 if문을 걸어 그냥 바로 출력하게끔 했는데,,,,, return 0;을 안줘서

- 계쏙 88퍼 쯤에서 틀렸습니다....ㅎ...한참 고민했는데 어이가 없었네요.....기본적인 실수를 줄이도록...해야겠습니다...

3. 나의 코드

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


int N;
string inputs;
vector<long long> maxresult;
long long tmpnum;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
void dfs(int index, long long nowvalue) {
	if (index >= N - 1) {
		maxresult.push_back(nowvalue);
		return;
	}
	tmpnum = cal(nowvalue, inputs[index + 2] - '0', inputs[index + 1]);
	dfs(index + 2, tmpnum);
	if (index + 4 <= N - 1) {
		long long first = cal(inputs[index + 2] - '0', inputs[index + 4] - '0', inputs[index + 3]);
		tmpnum = cal(nowvalue, first, inputs[index + 1]);
		dfs(index + 4, tmpnum);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	if (N == 1) { cout << inputs[0] - '0' << "\n"; return 0; }
	dfs(0, inputs[0] - '0');
	sort(maxresult.begin(), maxresult.end());
	cout << maxresult[maxresult.size() - 1] << "\n";
	return 0;
}

<오답 코드>  ---- 지적해주세요 !ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

long long dp[20]; // 결과를 저장할 테이블
int N;
string inputs;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	dp[0] = inputs[0] - 48;
	dp[2] = cal(inputs[0] - 48, inputs[2] - 48, inputs[1]);
	if (N == 1) { cout << dp[0] << "\n"; return 0; }
	if (N == 3) {cout << dp[3] << "\n"; return 0;}
	for (int i = 4; i < N; i += 2) {
		long long first = cal(inputs[i - 2] - 48, inputs[i] - 48, inputs[i - 1]);
		first = cal(dp[i - 4], first, inputs[i - 3]);
		long long second = cal(dp[i - 2], inputs[i] - 48, inputs[i - 1]);
		dp[i] = max(first, second);
	}
	cout << dp[N - 1] << "\n";
	return 0;
}

1. 다이나믹 프로그래밍 이란?

- Space(공간)을 더 사용하여 re-computing(중복되는 연산)을 방지하여 

  Speed(속도)를 증가시켜주는 방법입니다..

- solution 테이블을 사용하여 이미 연산된 적이 있다면 그 값은 바로 테이블에서 가져와서 쓰는 것입니다.

- 처음하는 연산의 경우 연산을 수행한 뒤 결과값을 solution table에 저장합니다.

- 일반적으로 최적해(Optimal Solution)을 구하는 데에 많이 사용된다.

2. Divide and Conquer(분할정복)과 차이점?

- 분할정복 역시 큰 문제를 작은 문제로 쪼개서 해결한다.

- 차이점은 DP에서는 부분(작은) 문제의 해가 중복되는 부분이 있어 나중에 또 필요하다는 것.

3.대표적인 예시

 (1) 피보나치 수열

     -피보나치 수열을 모든 연산을 반복적으로 수행하게끔 구현하면 n이 증가함에 따라

       총 연산의 수 가 급격히 높아진다.(중복되는 연산이 매우 많음)

-f(6)만 해도 이렇게 중복되는 연산이 많습니다.

- 빨간색은 연산없이 바로 테이블에서 끌어오는 녀석입니다.

(2) Matrix-Chain Multiplication 문제

- n개의 행렬이 주어졌을 떄 곱셈연산수를 가장 적게 하는 방법을 찾아라.

- (1~n)을 (1~k) * (k~n)으로 나누어야 하는데 어디를 나눌 것인가?

- 점화식과 관련이 깊다.

4. 해결절차

- (1) 최적해를 정의 한다.

- (2) 이를 바탕으로 점화식으로 표현한다

- (3) 바텀업방식이나 탑다운방식으로 이를 계산해 나간다.

5.구현방식

-(1) 바텀업 방식(Bottom-Up Approach)

     : 반복문 사용

       문제의 전체적인 구조를 파악하고 있어야 한다.

       재귀를 사용할 때의 오버헤드를 줄일 수 있다.

-(2) 탑다운 방식(Top-Down Approach)

     : 점화식의 구조를 직관적으로 파악하기 편하다.

       재귀함수 사용

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

간단한 다이나믹 프로그래밍 문제라고 할수 있겠습니다.

사실 처음 할때 개념을 이해하기가 꽤 힘들었던 것 같았던 기억이 있습니다....

이번에 아이패드를 사면서 사용하면서 풀고 있는데 보면서 약간 이해를 도울 수 있었으면 좋겠네요

목표지점 n으로 가기 위해 정수 123만 사용할수 있기 때문에

4이상의 숫자들은  1칸 가고 목표지점에 가는 경우의 수 dp[n-1]

                        2칸 가고 목표지점에 가는 경우의 수 dp[n-2]

                        3칸 가고 목표지점에 가는 경우의 수 dp[n-3]

으로 이해하시면 편하지 않을까 생각합니다.

<필기>

<코드>