작은시작

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

코드 설명

DP 메모리제이션 방식 + DFS을 합친 좋은 문제였던 것 같다.

어디 코테를 보면서 비슷한 걸 본 적이 있었는데 그 당시에 못 풀었어서 이문제는 복습을 계속해봐야 할 것 같다.

문제의 경우 DP맵 , 대나무 숲 맵 두 개로 나누어 서로 비교하며 문제를 풀어나가야 한다.

DP[y][x] : 그곳에서 시작하였을 때의 최대 이동 칸수 

즉, DP[y][x]에 값이 있다는 것은 굳이 들어가지 않아도 된다는 것을 의미한다. (이미 최대 경로가 들어가 있음)

이후에는 dfs(ny,nx)+1 을 통해 1씩 경로수를 늘려주며 재귀 탐색을 한다.

코드

//대나무먹고 자리옮기면 옮기려는 지역이 대나무가 더 많아야함(상하좌우)
//최댓값찾기
//전체탐색
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
int map[501][501];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int dp[501][501];
int dfs(int y, int x) {
	
	if (dp[y][x]) return dp[y][x]; // dp map에 값이 있다면 탐색하지 않고 리턴
	dp[y][x] = 1; // 없으면 처음 1부터 시작

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (map[ny][nx] <= map[y][x]) continue;
		dp[y][x]= max(dp[y][x], dfs(ny, nx)+1);


	}

	return dp[y][x];  // 4방향 전부 작을때 기존 dp return


}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];

		}
	}

	int answer = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			answer = max(answer, dfs(y, x));
		}
	}

	cout << answer;



	return 0;
}

www.acmicpc.net/problem/1463

코드 설명

바텀 업 방식의 DP 테이블을 이용한 DP 문제이다. DP문제 너무 오랜만에 풀어서 약간 당황했다...

원리는 1부터 목표값까지 연산수를 인덱스로 넣어 계속해서 비교한다.

3가지 케이스를 for문 한번마다 비교하여 더 작은 연산수를 찾는다.

-1같은 경우 모든 숫자에서 가능하기 때문에 기본값으로 넣어준후 나누기2,나누기 3과 계속해서 비교한다.

코드

#include<iostream>
#include<vector>
using namespace std;
int arr[1000001];
int main() {
	int n;
	cin >> n;
	arr[1] = 0;

	for (int i = 2; i <= n; i++) { //3가지 case비교하여 가장 min값 넣기
		arr[i] = arr[i-1] + 1; // arr[2] = arr[1] +1 에서 시작
		if (i % 3 == 0) {
			arr[i] = min(arr[i], arr[i / 3] + 1); // arr[6]일때 18에서 3으로 나눈경우, 7에서 1을 뺀경우 둘중 작은걸 넣어줌

		}
		if (i % 2 == 0) {
			arr[i] = min(arr[i], arr[i / 2] + 1);
		}

	}
	cout << arr[n];



	return 0;
}