2. 알리바바와 40인의 도둑

    2번 문제   

 

 

---

    내가 풀이한 답   

 

 Bottom-up 방식으로 접근하였고 이차원 배열에서 접근할 수 있는 경우의 수를 생각해 보았다. 현재 기준에서 오른쪽과 아래쪽으로만 갈 수 있기 때문에 총 3가지의 경우의 수가 존재했다. 

 

 첫 번째는 보라색 부분과 같이 오른쪽에서만 올 수 있는 경우였다. 이는 왼쪽 값과 입력된 값을 더해주었다.

 두 번째는 하늘색 부분가 같이 아래쪽에서만 올 수 있는 경우였다. 이는 위쪽 값과 입력된 값을 더해주었다.

 마지막으로는 오른쪽과 아래쪽 둘 다 올 수 있는 경우였다. 이는 오른쪽과 아래쪽 중 제일 작은 값을 찾아 입력된 값을 더해주었다. 

 

 

#include <algorithm>
using namespace std;

int arr[21][21];
int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);

	int n, i, j, a;
	cin >> n;
	
	for(i=1; i<=n; i++){ 
		for(j=1; j<=n; j++){
			cin >> a;
			if(i==1 && j==1) arr[i][j] = a;
			else if(i==1 && j!=1) arr[i][j] = arr[i][j-1] + a;
			else if(j==1 && i!=1) arr[i][j] = arr[i-1][j] + a;
			else arr[i][j] = min(arr[i-1][j], arr[i][j-1]) + a;		
		}
	}	
	
	cout << arr[n][n];
	return 0;
}

 

 

 결과는 통과하였다.

 

 

---

    사이트의 답안   

 

#include<bits/stdc++.h>
using namespace std;
int arr[21][21], dy[21][21];
int main(){
	ios_base::sync_with_stdio(false);
	freopen("input.txt", "rt", stdin);
	int n, cnt=0;
	cin>>n;
    
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>arr[i][j];
		}
	}
    
	dy[0][0]=arr[0][0];
	for(int i=1; i<n; i++){
		dy[0][i]=dy[0][i-1]+arr[0][i];
		dy[i][0]=dy[i-1][0]+arr[i][0];
	}
    
	for(int i=1; i<n; i++){
		for(int j=1; j<n; j++){
			dy[i][j]=min(dy[i-1][j], dy[i][j-1])+arr[i][j];
		}
	}
	cout<<dy[n-1][n-1];
	return 0;
}

 

  사이트의 답도 3가지 경우의 수로 나눠서 접근했다. 위쪽에서 오는 경우와 왼쪽에서 오는 경우를 한 번에 처리하는 부분이 좀 인상 깊었다. 나는 왜 저 생각을 못했을까

 

---

 

    또 다른 방법 - Top Down 방식   

 

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

int arr[21][21], dp[21][21];

int dfs(int a, int b){
	if(dp[a][b]>0) return dp[a][b];
	if(a==1 && b==1) return arr[1][1];
	else {
		if(a==1 && b!=1) return dp[a][b] = dfs(a, b-1) + arr[a][b];
		else if(b==1 && a!=1) return dp[a][b] = dfs(a-1, b) + arr[a][b];
		else  return dp[a][b] = min(dfs(a-1, b), dfs(a, b-1)) + arr[a][b];
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);

	int n, i, j;
	cin >> n;
	
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			cin >> arr[i][j];
		}
	}
	
	cout << dfs(n, n);
	return 0;
}

 

  사이트의 답과 논리적으로 똑같았다.