알못에서 잘알까지

    4번 문제   

    내가 풀이한 답   

 장애물이 없는 경우와 장애물이 있는 경우를 살펴보면 장애물이 없을 때 (1, 1)에서 (3, 3)까지 갈 수 있는 방법은 6가지이고 장애물이 있을 때에는 2가지이다. 

 한 칸 아래 또는 한 칸 오른쪽으로 갈 수 있으므로 점화식은 f(m, n) = f(m-1, n) + f(m, n-1)이다. 장애물 같은 경우는 갈 수 있는 경우의 수가 0이므로 0으로 설정해준다. 

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

int a[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0; i<puddles.size(); i++){
        a[puddles[i][0]][puddles[i][1]] = -1;
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(i==1 && j==1) a[i][j] = 1;
            else if(a[i][j] == -1) a[i][j] = 0;
            else a[i][j] = (a[i-1][j] + a[i][j-1])%1000000007;
        }
    }
    return a[m][n];
}

 결과는 통과하였다.

    3번 문제   

    내가 풀이한 답   

 Bottom-up 방식으로 접근하였고 2번 알리바바와 40인의 도둑과 매우 비슷한 유형의 문제라고 생각했다. 정수 삼각형 역시 경우의 수를 생각해 보았다. 

 첫 번째는 보라색 부분과 같이 오른쪽 대각선으로만 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 해당 위치의 값을 더해주었다.

 두 번째는 하늘색 부분가 같이 왼쪽 대각선으로만 올 수 있는 경우였다. 이는 위쪽 값과 해당 위치의 값을 더해주었다.

 마지막으로는 오른쪽과 왼쪽 대각선으로 둘 다 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 위쪽 값 중 제일 작은 값과 해당 위치의 값을 더해주었다.  

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

int arr[500][500];
int solution(vector<vector<int>> triangle) {
    int i, j, ans=0;
    for(i=0; i<triangle.size(); i++){
        for(j=0; j<triangle[i].size(); j++){
            if(i==0 && j==0) arr[i][j] = triangle[i][j];
            else if(j==triangle[i].size()-1) arr[i][j] = arr[i-1][j-1] + triangle[i][j];
            else if(j==0 && i!=0) arr[i][j] = arr[i-1][j] + triangle[i][j];
            else arr[i][j] = max(arr[i-1][j-1], arr[i-1][j]) + triangle[i][j];
        }
    }
    for(i=0; i<triangle[triangle.size()-1].size()-1; i++){
        ans = max(ans, arr[triangle.size()-1][i]);
    }
    return ans;
}

 결과는 통과하였다.

    다른 사람들의 풀이   

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {

    //바닥부터 큰 값의 수를 윗 칸에 더해나간다
    for(int i = triangle.size()-2; i > -1; i--){
        for(int j = 0; j <= i; j++){
            triangle[i+1][j] > triangle[i+1][j+1] ? triangle[i][j] += triangle[i+1][j] : triangle[i][j] += triangle[i+1][j+1];
        }
    }

    return triangle[0][0];
}

 제일 끝 부분부터 큰 값의 수를 더해간다는 것이 인상 깊었다. 전혀 생각지도 못한 풀이였다.

    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;
}

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

    1번 문제   

    내가 풀이한 답   

 Bottom-up 방식으로 직관적으로 구할 수 있는 작은 해들을 구하고 그 작은 해를 이용해서 큰 해를 차례로 구해서 점화식을 도출하였다. 

#include <iostream>
using namespace std;

int a[50];
int main() {
	//freopen("input.txt", "rt", stdin);

	ios_base::sync_with_stdio(false);
	int n, i; 
	cin >> n;
	
	a[1] = 1;
	a[2] = 2;
	
	for(i=3; i<=n; i++){
		a[i] = a[i-2] + a[i-1];
	}
	
	cout << a[n];
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

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

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

    또 다른 방법 - Top Down 방식   

 Top-Down 방식으로도 풀 수 있는데 이 방식은 재귀 + 메모이제이션을 이용한 방식이다. 아래 그림과 같이 재귀식으로 함수를 호출하고 입력 값이 큰 수일수록 반복되는 재귀 함수가 많으므로 시간이 오래걸리기 때문에 메모이제이션 방식으로 한 번 호출한 적이 있으면 그 값을 바로 리턴해서 시간복잡도를 줄일 수 있다. 

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

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