대엉코딩

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

1. 풀이방법

- 최대 깊이가 500입니다.

- 모든 경우의 수를 모두 구하면 매우 커짐을 알 수 있습니다.

- 점화식을 세우고, 0과 i==j 일때 (한변에서 양 끝은 선택권이 한개씩 뿐) 처리를 따로 해주시면 됩니다.

- 바텀업 방식으로 작성했습니다.

2. 주의사항

- 없음

3. 나의코드

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

int triangle[500][500];
int dp[500][500];
int n;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			cin >> triangle[i][j];
			dp[i][j] = -1;
		}
	}
	dp[0][0] = triangle[0][0];
	
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i + 1; j++) {
			if (j == 0) {
				dp[i][j] = dp[i - 1][j] + triangle[i][j];
			}
			else if (j == i) {
				dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
			}
		}
	}
	int maxr = -1;
	for (int i = 0; i < n; i++) {
		maxr = max(dp[n - 1][i], maxr);
	}
	cout << maxr << "\n";
	return 0;
}

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

1. 풀이방법

- 처음에는 단순 dfs로 접근하긴 했지만 (오랜만에 풀이라 일단 접근했음)

- 하면서도 분명 제대로 구현되도 시간초과가 뜨거나 스택오버플로우가 날 것 이라 생각했습니다.

- 처음시도는 역시나 시간초과

- 시간초과라면 dp테이블을 이용해보자는 생각 !

- 아, 근데 오랜만에 푸니까 dp적 머리가 잘 돌아가지 않아서 고생을 좀 했습니다....

- 우선 테이블을 모두 -1 처리를 하고 visit이 이미 true인 곳에 다시 오면 그건 싸이클이므로

- -1을 출력 (무한정 왔다리갔다리 가능)

- dp가 -1이 아닐경우 기존에 저장되어 있는 수와 현재의 루트에서 +1 (한번 더 이동) 해서 더 많은 이동횟수로 업데이트

- dfs +dp 라고 할 수 있겠네요. dfs는 간단한 수준이라 생략하겠습니다.

2. 주의사항

- 시간초과

3. 코드

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define endl "\n"
using namespace std;

int N, M;
int ground[50][50];
int dp[50][50];
bool visited[50][50];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


void Input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        string inputs;
        cin >> inputs;
        for (int j = 0; j < inputs.length(); j++){
            if (inputs[j] == 'H') ground[i][j] = 0;
            else ground[i][j] = inputs[j] - '0';
        }
    }
}

int DFS(int x, int y){
    if (x < 0 || y < 0 || x >= N || y >= M || ground[x][y] == 0) return 0;
    if (visited[x][y] == true) // 무한반복이 가능
    {
        cout << -1 << endl;
        exit(0);
    }
    if (dp[x][y] != -1) return dp[x][y]; // 바로 dp 테이블에서 리턴

    visited[x][y] = true;
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++){
        int tx = x + (ground[x][y] * dx[i]);
        int ty = y + (ground[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(tx, ty) + 1);
    }
    visited[x][y] = false;
    return dp[x][y];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Input();
    memset(dp, -1, sizeof(dp)); //dp 테이블 초기화
    cout << DFS(0, 0) << endl;
    return 0;
}

www.acmicpc.net/problem/1793

1. 풀이방법

- 점화식을 찾는 것은 어렵지 않습니다.

- 그림 몇개 그려보고 생각 해보면 dp[i]=dp[i-1]+dp[i-2]*2 입니다.

- 하지만 더 큰 문제는 c++에서 제공해주는 정수 자료형으로는 이 문제의 출력을 담아 낼 수 없습니다.

- 그래서 저 같은 이차원으로 벡터를 이용해서 벡터의 한 원소당 한 자리의 숫자를 담아서 표현하였고,

- 점화식을 보면 기껏해야 2를 곱하는 것이기 때문에 이것은 그냥 더하기로 구현이 가능하기 때문에

- 큰 정수의 덧셈을 구하는 함수만 작성하여 해결하였습니다.

2. 주의사항

- 일단 dp[0]=1 입니다 (  nCo = 1 인 것과 같이) -- 아무것도 선택 안함

- 그리고 처음에 while(EOF) 를 이용하여 입력을 제어 했는데, 출력초과가 계속 나와서 

- 이부분을 , while (cin>>n)로 해결했습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;




vector<int> bigintadd(vector<int> v1, vector<int> v2) {

	if (v1.size() < v2.size()) { // v1이 항상 더 큰수
		vector<int> tmpv = v1; v1 = v2; v2 = tmpv;
	}
	vector<int> result(v1.size());
	for (int i = 0; i < v1.size(); i++) {
		result[i] = 0;
	}
	if (v1.size() == v2.size() && (v1[v1.size() - 1] + v2[v2.size() - 1]) >= 10) {
		result.push_back(0); //사이즈 하나 증가
	}

	for (int i = 0; i < v2.size(); i++) {
		int tmpi = v1[i] + v2[i]+result[i];
		if (tmpi >= 10) { result[i + 1] += 1; result[i] =( tmpi-10); }
		else result[i] = tmpi;
	}
	for (int i = v2.size(); i < v1.size(); i++) {
		result[i] += v1[i];
	}

	return result;
}

// 점화식 dp[i]=dp[i-1]+dp[i-2]*(3-1)
// 큰수의 곱을 구현해야 한다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	vector<int> dp[251];
	dp[0].push_back(1); dp[1].push_back(1); dp[2].push_back(3);
	for (int i = 3; i <= 250; i++) {
		dp[i] = bigintadd(dp[i - 1], bigintadd(dp[i - 2], dp[i - 2])); //8은 171 7은 85   171+85+85
	}
	int n;
	while (cin>>n) {
		for (int i = dp[n].size() - 1; i >= 0; i--) {
			cout << dp[n][i];
		}
		cout << "\n";
	}
	return 0;
}

www.acmicpc.net/problem/1965

1. 풀이방법

- 간단하게 생각하면 매우 간단합니다. 

- 저 같은 경우 처음에 막혔던 부분이 보통의 dp문제에서 dp테이블은 각각의 n에 따른 정답? 을 가지고 있습니다.

- 이런식으로 짜려고 고민을 하다 보니 상당히 구현이 까다로웠습니다.

- 예를 들면 테스트케이스 가 1, 6, 2, 5, 7, 3, 5, 6   총 8개 인데

- 보통의 dp 테이블이면 만약 dp[6]을 뽑으면 최대치는 1,2,5,7 로서 4가 나와야 하고 

- 이때의 상자의 바깥껍질의 크기인 7을 저장하면 dp[7]을 구하려고 할 때 1,2,5,7,과 1,2,3, +5 를 비교하는 것이 힘들었습니다.

- 설명하기가 조금 곤란한데, 비슷한 고민을 하신 분들은 공감을 하시리라....조심스럽게 생각해봅니다....

- 그래서 이 문제의 경우 n이하의 각각의 정답(즉 최대 상자의 수)를 dp에 저장하는 것이 아니라 

- n에 크기를 늘려가면서 그때까지 차곡차곡 쌓기만한 크기를 저장해 놓은 다음 출력 전에 정렬을 해서 max 값을 

- 출력하였습니다. 물론 정렬(소팅)을 하지않고 최대값만 갱신해도 상관 없습니다.

- 이런식으로 할경우 사실 정렬 전에 dp[6]에는 상자의 개수 3 (1,2,3) dp[5]에는 4 (1,2,5,7) 이 들어가 있습니다.

- 그러므로 n이 6일 때의 정답이 테이블에 들어가 있는 것은 아닌 것이죠. 정렬을 해서 출력을 해줘야 정답이 나오는 

- 것 입니다. 하지만 이렇게 하면 문제의 요구사항에는 전혀 에러가 없고, 구현이 편해집니다.

2. 주의사항

- 위에 기재.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int dp[1001]; // 사실상 정확한 dp를 가지고 있는 테이블은 아니다.
int n;
int narr[1001]; //상자의 크기


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { //초기화
		cin >> narr[i]; dp[i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (narr[i] > narr[j] && dp[i]<dp[j]+1) {
				dp[i] = dp[j]+ 1;
			}
		}
	}
	sort(dp + 1, dp + (n + 1));
	cout << dp[n];

	return 0;
}

www.acmicpc.net/problem/1463

1. 풀이방법

- 맨 처음에는 3으로 나누어떨어지면 -> 2로 나누어떨어지면 -> 이것마저 안되면 -1 이라고 생각했었는데

- 이럴경우 10->5->4->2->1  (답은 10->9->3->1)

- 그리고 나서 숫자를 쭉 써놓고 한번생각을 해보았는데

- 결국 비교해야 할 경우는 3가지 이다 N-1 과 N/3 과 N/2 이다.

- 중요한 것은 경우에 따라 N-1을 한 경우가 최소연산 일 수 있다는 것.

2. 주의사항

- 처음에는 항상 익숙한대로 탑다운 방식(재귀함수)를 이용했다.

-결과는 "메모리 초과"

- 문제 조건을 보았는데 메모리는 128MB까지 허용이 가능하고

- 내가 사용한 용량을 얼추 계산해봐도 1,000,000 * 4바이트(INT) 기껏해서 4MB 정도이다. (짜잘한 것은 생략.)

- 추측한 것은 재귀로 너무 깊이 들어가서 스택메모리가 초과되었나? 라는 생각

- 그래서 재귀를 사용하지 않고 바텀업 방식(반복문이용) 으로 짰더니 통과가 되었습니다.

3. 나의코드

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

int X;
int dp[1000001];

//메모리 초과
/*int getdp(int num) {
	if (dp[num] == 0) {
		if (num % 3 == 0) { dp[num] = min((getdp(num - 1) + 1), (getdp(num / 3) + 1)); return dp[num]; }
		else if (num % 2 == 0) { dp[num] = min((getdp(num - 1) + 1),(getdp(num / 2) + 1)); return dp[num]; }
		else { dp[num] = getdp(num - 1) + 1; return dp[num]; }
	}
	else { return dp[num]; }
}*/
void bottomup() {
	for (int i = 6; i < 1000001; i++) {
		if (i % 3 == 0) {dp[i] = min(dp[i - 1] + 1, dp[i / 3] + 1);}
		else if(i%2==0){ dp[i] = min(dp[i - 1] + 1, dp[i / 2] + 1); }
		else { dp[i] = dp[i - 1] + 1; }
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> X;   //  X>1
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[4] = 2;
	dp[5] = 3;
	bottomup();
	cout<<dp[X]<<"\n";
	return 0;
}

www.acmicpc.net/problem/11048

1. 풀이방법

- 다이나믹프로그래밍을 이용해서 탑다운 방식으로 해결하였습니다.

- 저 같은 경우 1행의 모든 값과 1열의 모든 값들은 가로 또는 세로로 쭉 이동하는 경우밖에 없으므로

- 초기화할 때 먼저 쭉 작업을 해서 dp 테이블에 넣어놓은 후 시작하였습니다.

2. 주의사항

- 주의사항은 아니고 풀고난 후에 생각난 건데 얻을 수 있는 최대의 사탕의 수를 구하는 것이므로

- 대각선 이동은 빼도 될 것 같습니다.

- 사탕을 뺏어간다는 조건이 있지 않은 이상 대각선이 가로->세로, 또는 세로->가로 로 이동하는 것 보다 많은 사탕을 얻을 수는 없기 때문에 사실 확인하지 않아도 될 것입니다.

3. 나의코드

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

int N, M;
int candymap[1001][10001];
int dp[1001][1001];

void inputs() {//기본셋팅
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> candymap[i][j];
			dp[i][j] = -1; //dp테이블은 -1로 초기화
		}
	}
	dp[1][1] = candymap[1][1];
	for (int i = 2; i <= N; i++) {
		dp[i][1] = dp[i - 1][1]+candymap[i][1];
	}
	for (int j = 2; j <= N; j++) {
		dp[1][j] = dp[1][j-1]+candymap[1][j];
	}
}
int maxthree(int num1, int num2, int num3) {
	int tmp = max(num1, num2);
	tmp = max(tmp, num3);
	return tmp;
}
int getdp(int x, int y) {
	if (dp[x][y] != -1) return dp[x][y];
	else {
		dp[x][y] = maxthree(getdp(x - 1, y), getdp(x, y - 1), getdp(x - 1, y - 1))+candymap[x][y];
		return dp[x][y];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	cout << getdp(N,M) << "\n";
	return 0;
}

www.acmicpc.net/problem/11726

1. 풀이방법

- 이 문제를 접할 때 점화식을 생각해내는 게 생각보다 어려웠습니다.

- 물론 이런 류의 문제는 알고나면 매우 간단하기는 하지만......!

- 결국 점화식은 dp[n]=dp[n-1] + dp[n-2] 입니다 

- 그림을 보시면 이해가 쉬우실 듯 합니다.

2. 주의사항

- 값을 저장할 테이블을 구성해서 메모이제이션을 활용하여 시간을 단축시켜주었습니다.

- 탑다운 방식으로 재귀함수만을 이용하여 연산하는 경우 중복되는 연산을 너무나 많이 하기때문에

- TIME LIMIT을 만나실 수 있습니다.

- 저장되어있는값이 있으면 바로 리턴해서 가져다 쓰고 새로운 값이면 테이블에 저장을 한 후 리턴해서

- 다음부터는 그 값이 필요할 때 테이블에서 바로 가져다 쓸 수 있도록 하면 됩니다.

3. 나의코드

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

int  n;
int dp[1001];

int getdpvalue(int num) {
	if (dp[num] == 0) { 
		dp[num] = (getdpvalue(num - 1) % 10007 + getdpvalue(num - 2) % 10007);
		return dp[num] % 10007;
	}
	else return dp[num]%10007;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	dp[1] = 1; dp[2] = 2; dp[3] = 3; // 3을 초기화안해줘도 되긴하다
	                                 // (하지만 경우의수 그림 그려놨으니까..아까워서)
	cout<<getdpvalue(n)<<"\n";

	return 0;
}

www.acmicpc.net/problem/7570

1. 풀이방법

 - 몇가지 예시를 직접 종이에 써서 알아보고, 코드로도 짜보고 하면서 알아낸 것이

 - 순방향(? 증가하는) 쪽의 가장 긴 증가수열의 길이를 알아내는 것이 핵심 이었습니다.

 - 근데 한번의 작업으로 맨 앞 혹은 맨 뒤 양 끝으로만 보낼 수 있기 때문에 그냥 최장증가수열이 아닌 !

 - 1씩 증가하는 최장증가수열의 길이를 구해야 했습니다!!!!

 - 입력의 범위를 보니 이중반복문이 들어갈 경우 시간초과가 명백하여서 dp를 통해서 입력을 받으면서 구했습니다.

2. 주의사항 

 - 지금보면 단순해보이는 numarr[tmp]=numarr[tmp-1]+1 이 것을 생각해내는 게 꽤 어려웠습니다 ㅠㅠㅠ

 - dp에 익숙하지 않아서 일까요...꽤 오래걸렸습니다...

 - 보시는 분들 중에 이해가 안되는 분들은 임의의 길이 7 정도의 입력을 직접 그려보면서 써가면서 하시면 

 - 이해가 잘 되실 것 같습니다.

3. 나의코드

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

int N;
int numarr[1000001];
int maxlistcount;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp; 
		numarr[tmp] = numarr[tmp - 1] + 1;
		maxlistcount = max(maxlistcount, numarr[tmp]);
	}
	cout << N - maxlistcount << "\n";
	return 0;
}