말하는감자의 공부기록

c++ 백준 1520 내리막길

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

해설

⚡ dp[N][M] : 좌표가 (N,M) 일 때 가능한 경로 수

⚡ dp는 -1로 초기화 한다

                 : 경로가 하나도 없을때 0 , N개의 경로가 있을 때 , 방문하지 않았을 때 -1

                 : 방문하지 않았을 때를 검사하기 위해서!

⚡ 시작 좌표에 대해서 DFS

                -> "계단수"이면 dfs로 재귀

                -> if 좌표가 범위를 벗어난다면?  탈출가능, 경로가 하나니까 return 1

                -> if 좌표가 목적지 N-1 , M-1에 도달했다면 ? 경로가 하나니까 return 1   

                -> if 방문했으면 ? 해당 좌표의 dp에 저장된 경로수를 return          

⚡ dfs이해가 안되서 하나하나 그려봤다 
  : dp [N-1][M-1]을 출력하는 것이 아닌 dp[0][0]를 출력해야 한다 (내가 생각한거랑 반대였다....)

코드 

int N , M;
const int MAX = 501;
int arr[MAX][MAX];
int dp[MAX][MAX];

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

int dfs(int x, int y) // dp는 -1로 초기화되어있음
{
	if (x == N - 1 && y == M - 1) // 도착지에 도착하면 ?
	{
		return 1;
	}
	if (dp[x][y] != -1) //방문했으면? 
	{
		return dp[x][y];
	}

	dp[x][y] = 0; //방문은 했으니까 0으로
	for (int i = 0; i < 4; i++)
	{
		int mx = x + dx[i];
		int my = y + dy[i];

		if (mx < 0 || my <0 || mx >= N || my >M) 
		{
			continue;
		}
		
		// 계단수여서 다음으로 넘어갈수 있으면?
		if (arr[mx][my] < arr[x][y]) 
		{
			dp[x][y] = dp[x][y] + dfs(mx, my);
		}
	}

	// 최종 정답을 return?
	return dp[x][y];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//백준 1520
	cin >> N >> M;

	for(int i =0;i<N;i++)
	{
		for (int j = 0; j < M; j++) 
		{
			cin >> arr[i][j];
		}
	}
	
	memset(dp, -1, sizeof(dp)); 
	// dp[][]가 -1 : 아직 방문하지 x
	// dp[][]가 0 : 0개 

	int answer = dfs(0, 0);
	cout << answer;
}

https://github.com/churush912837465

C++ / 백준 2193 이친수  

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

해설

⚡dp[N] : 길이가 N인 이친수의 갯수

⚡dp[3] = dp[1] + dp[2] 

⚡dp[4] = dp[2] + dp[3]

....

⚡피보나치 수열이랑 같은 점화식!

코드

⚡dp의 자료형을 'long long'으로 해야함! 

int N;
int M;
long long dp[91];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// 백준 2193
	cin >> N;
	
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 3; i <= N; i++) 
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[N];

}

https://github.com/churush912837465

C++ / 백준 2294 동전2

문제 

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

해설

1️⃣dp의 초기값을 "최대값"으로 설정 

	#define INF 123456789
    
    	for (int i = 0; i <= N; i++)
	{
		dp[i] = INF;
	}

2️⃣coin이 1일때

⚡coin이 1일때 , 만들 수 있는 값의 범위가 1~N

3️⃣coin이 5일때

⚡coin이 5일때 , 만들 수 있는 값의 범위가 5~N

4️⃣coin이 12일때

⚡coin이 12일때 , 만들 수 있는 값의 범위가 12~N

코드

using namespace std;
#include <iostream>
#include <vector>
#include <algorithm> // sort

#define MAX 10001
#define INF 123456789

int N;
int M;
int coin[MAX];
int dp[MAX];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	// 백준 2294 동전2
	cin >> N >> M;

	// dp 배열에 작은 동전부터 개수 갱신, 
	// 다음동전이랑 최솟값 저장
	for (int i = 0; i < N; i++)
	{
		cin >> coin[i]; // 동전 담아놓는 배열
	}

	// 최소값을 구해야 하기 때문에
	for (int i = 0; i <= M; i++) {
		dp[i] = INF;
		//dp배열에 최댓값으로 설정
	}

	dp[0] = 0;
	// dp[n] = 합이 n인 동전 갯수
	for (int i = 0; i < N; i++) // 1 5 12
	{
		for (int j = coin[i]; j <= M; j++)
		{
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
			// 1일때는 처음부터~15
			// 5일때는 5~15
			// 12일때는 12~15
		}
	}

	if (dp[M] == INF)
	{
		cout << -1;
	}
	else
	{
		cout << dp[M];
	}

https://github.com/churush912837465