[문제 링크]

 

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�

www.acmicpc.net


https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제였다.

 

TopDown으로 푸는 경우 현재 위치(Y, X)에서 다음 위치로 가는 경우가 (Y-1, X-1)과 (Y-1, X)만 존재하기 때문에 (Y-1, X-1) 이 가질 수 있는 최대값과 (Y-1, X) 이 가질 수 있는 최대값을 비교하여 더 큰 경우를 선택하면 된다.

함수를 재귀 호출하는 방법으로 이를 구현할 수 있으며, 기저사례로 X가 범위에 속하지 않을 경우 0을 반환하고, Y가 0일 때 즉, 삼각형의 꼭대기에 도달했을 때 그 위치의 정수값을 반환하도록 하였다.

 

BottomUp으로 푸는 경우 현재 위치(Y, X)가 가질 수 있는 최대값은 (Y-1, X-1)의 최대값과 (Y-1, X)의 최대값 중 더 큰 값에 현재 위치(Y, X)의 정수값을 더해줌으로써 구할 수 있다. 

TopDown과 마찬가지로 X가 범위에 속하지 않는 경우 최대값이 존재할 수 없기 때문에 계산하지 않도록 구현하였다.


#include <iostream>
#include <cstring>
using namespace std;

int n, tri[501][501], memo[501][501];

inline int max(int a, int b) { return a > b ? a : b; }

int TopDown(int hereY, int hereX)
{
	if (hereX < 0 || hereX > hereY) return 0;
	if (hereY == 0) return tri[hereY][hereX];

	int& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	int val = tri[hereY][hereX];
	return ret = max(TopDown(hereY - 1, hereX - 1), TopDown(hereY - 1, hereX)) + val;
}

int BottomUp(int n)
{
	memo[0][0] = tri[0][0];

	for(int i = 1; i<n; i++)
		for (int j = 0; j < i + 1; j++)
		{
			int val = tri[i][j];
			if (j == 0)
				memo[i][j] = memo[i - 1][j] + val;
			else
				memo[i][j] = max(memo[i - 1][j - 1], memo[i - 1][j]) + val;
		}

	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, memo[n - 1][i]);

	return res;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];

	// Top-Down
	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, TopDown(n - 1, i));
	cout << "TopDown: " << res << endl;
	
	// Bottom-Up
	cout << "BottomUp: " << BottomUp(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 64 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2156번: 포도주 시식  (0) 2020.06.09
백준 2193번: 이친수  (0) 2020.06.08
백준 2579번: 계단 오르기  (0) 2020.06.08
백준 1149번: RGB거리  (0) 2020.06.08
백준 11726번: 2 x n 타일링  (0) 2020.06.08

[문제 링크]

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net


TopDown 으로 푸는 경우 위에 계단을 밟았는지 안밟았는지 여부에 따라 다른 점화식으로 동작하도록 하였고, 위에 계단을 밟은 경우와 안밟은 경우의 최댓값을 다르게 저장하기 위해 2차원 배열로 메모이제이션 하였다.

기저사례로 현재 위치가 계단 범위를 벗어날 경우 값이 없으므로 0을 반환해주었다.

 

BottomUp 으로 푸는 경우 마찬가지로 아래 계단을 밟았을 경우와 안밟았을 경우의 값이 다르기 때문에 2차원 배열로 메모이제이션 하였다. 첫번째 계단과 두번째 계단을 미리 계산하여 결과값을 메모이제이션한 다음, 미리 계산한 값을 이용하여 세번째 계단부터 N번째 계단까지 계산하는 형태로 구현하였다.


#include <iostream>
#include <cstring>
using namespace std;

int N, stairs[301], memoTop[301][2], memoBot[301][2];

inline int max(int a, int b) { return a > b ? a : b; }

int TopDown(int here, int check)
{
	// check == 0 : 위에 계단 밟은 경우
	// check == 1 : 밟지 않은 경우
	if (here < 0) return 0; // 기저사례: 계단을 벗어났을 경우 0 반환

	int& ret = memoTop[here][check];
	if (ret != 0) return ret;

	if (check)
		ret = max(TopDown(here - 1, 0) + stairs[here], TopDown(here - 2, 1) + stairs[here]);
	else
		ret = TopDown(here - 2, 1) + stairs[here];

	return ret;
}

int BottomUp(int N)
{
	// memoBot[i][0] : 아래 계단 밟은 경우
	// memoBot[i][1] : 밟지 않은 경우
	memoBot[0][0] = memoBot[0][1] = stairs[0];
	memoBot[1][1] = stairs[1];
	memoBot[1][0] = stairs[0] + stairs[1];
    
	for (int i = 2; i < N; i++)
	{
		memoBot[i][1] = max(memoBot[i - 2][0], memoBot[i - 2][1]) + stairs[i];
		memoBot[i][0] = memoBot[i - 1][1] + stairs[i];
	}
    
	return max(memoBot[N - 1][0], memoBot[N - 1][1]);
}

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> stairs[i];

	// Top-Down
	cout << TopDown(N-1, 1) << endl;
    
	// Bottom-Up
	cout << BottomUp(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 64 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2193번: 이친수  (0) 2020.06.08
백준 1932번: 정수 삼각형  (0) 2020.06.08
백준 1149번: RGB거리  (0) 2020.06.08
백준 11726번: 2 x n 타일링  (0) 2020.06.08
백준 1003번: 피보나치 함수  (0) 2020.06.07

[문제 링크]

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net


https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제라고 생각한다.

 

N번째 집이 어떤 색으로 칠해진다면 N+1번째 집은 N번째 집이 칠해진 색깔을 제외한 색깔로 칠해져야 한다는 사실과 

N+1번째 집이 칠해진 색깔에 따라 N+2번째 집이 칠해지는 색깔도 정해진다는 사실을 생각한다면 어렵지 않게 풀이법을 떠올릴 수 있을 것이다.

 

동적계획법 문제는 Top-Down과 Bottom-Up으로 알고리즘을 구현할 수 있는데, 각각의 방식마다 장점과 단점이 존재한다.

필자는 두 가지 방식을 연습하기 위하여 Top-Down과 Bottom-Up 각각 구현하였다.


#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int house[1001][3], memo[1001][3];

inline int min(int a, int b) { return a < b ? a : b; }

int TopDown(int here, int color)
{
	if (here == 0) return house[here][color];

	int& ret = memo[here][color];
	if (ret != -1) return ret;

	ret = INF;

	for (int i = 0; i < 3; i++)
	{
		if (i == color) continue;
		ret = min(ret, TopDown(here - 1, i) + house[here][color]);
	}

	return ret;
}

int BottomUp(int N)
{
	memo[0][0] = house[0][0];
	memo[0][1] = house[0][1];
	memo[0][2] = house[0][2];

	for (int i = 1; i < N; i++)
		for (int j = 0; j < 3; j++)
		{
			int cost = house[i][j];
			if (j == 0) 
				memo[i][j] = min(cost + memo[i - 1][1], cost + memo[i - 1][2]);
			else if (j == 1) 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][2]);
			else 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][1]);
		}

	return min(memo[N - 1][0], min(memo[N - 1][1], memo[N - 1][2]));
}
int main(void)
{
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> house[i][j];

	// Top-Down
	int res = INF;
	for (int i = 0; i < 3; i++)
		res = min(res, TopDown(N - 1, i));		
	cout << res << endl;
	
	// Bottom-Up
	cout << BottomUp(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 63 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1932번: 정수 삼각형  (0) 2020.06.08
백준 2579번: 계단 오르기  (0) 2020.06.08
백준 11726번: 2 x n 타일링  (0) 2020.06.08
백준 1003번: 피보나치 함수  (0) 2020.06.07
백준 9095번: 1, 2, 3 더하기  (0) 2020.06.07

[문제 링크]

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net


간단한 DP 문제였다. 피보나치 수열과 비슷한(거의 같은) 점화식으로 풀 수 있다.

2 x n 타일을 채우는 경우의 수는 타일 가장 오른쪽을 세로블록 한개로 채우는 경우의 수와 가로블록 두개로 채우는 경우의 수의 합과 같기 때문이다.

따라서 점화식은 dp(n) = dp(n-1) + dp(n-2) 이며,

기저사례로 n == 1일 때 1을 반환, n == 2일 때 2를 반환하여 횟수를 카운팅 해주면 쉽게 원하는 결과를 얻을 수 있다.


#include <iostream>
#include <cstring>
using namespace std;

int memo[1001];

int Solution(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;

	int& ret = memo[n];
	if (ret != -1) return ret;

	return ret = (Solution(n - 1) + Solution(n - 2)) % 10007;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	int n;
	cin >> n;
	cout << Solution(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 63 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2579번: 계단 오르기  (0) 2020.06.08
백준 1149번: RGB거리  (0) 2020.06.08
백준 1003번: 피보나치 함수  (0) 2020.06.07
백준 9095번: 1, 2, 3 더하기  (0) 2020.06.07
백준 1463번: 1로 만들기  (0) 2020.06.07

[문제 링크]

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net


간단한 DP 문제였다. 0과 1이 호출되는 횟수를 카운팅하기 위해 pair 컨테이너를 사용하였고,

pair 컨테이너의 first 에는 0이 호출되는 횟수, second 에는 1이 호출되는 횟수를 저장하는 형태로 구현하였다.

 

끝으로 피보나치 함수의 점화식이 Sol(n) = Sol(n-1) + Sol(n+1) 인 것을 활용하면 원하는 결과를 얻을 수 있다.


#include <iostream>
using namespace std;

pair<int, int> memo[41];

pair<int, int> Solution(int n)
{
	if (n == 0 || n == 1) return memo[n];

	pair<int, int>& ret = memo[n];
	if (ret.first != -1 && ret.second != -1) return ret;

	pair<int, int> a, b;
	a = Solution(n - 1);
	b = Solution(n - 2);

	return ret = make_pair(a.first + b.first, a.second + b.second);
}

int main(void)
{
	for (int i = 2; i < 41; i++)
		memo[i] = make_pair(-1, -1);

	memo[0] = make_pair(1, 0);
	memo[1] = make_pair(0, 1);

	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		pair<int, int> res = Solution(n);
		cout << res.first << ' ' << res.second << endl;
	}
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1149번: RGB거리  (0) 2020.06.08
백준 11726번: 2 x n 타일링  (0) 2020.06.08
백준 9095번: 1, 2, 3 더하기  (0) 2020.06.07
백준 1463번: 1로 만들기  (0) 2020.06.07
백준 1300번: K번째 수  (0) 2020.05.22

[문제 링크]

 

9095번: 1, 2, 3 더하기

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는

www.acmicpc.net


간단한 DP 문제였다.

n을 1, 2, 3의 합으로 나타내는 방법의 수를 계산하는 함수를 Sol(int n) 이라고 할 때,

n이 10일 때 나올 수 있는 방법의 수 Sol(10)은  Sol(9) + Sol(8) + Sol(7) 과 같다.

 

따라서 기저사례로 n == 0 또는 n == 1 일 때 1을 반환하도록 하여 방법의 수를 카운팅하고

(n == 0일 때 1을 반환하는 이유는 n이 2 또는 3일 경우 숫자의 합이 아닌 2, 3 그 자체로도 표현할 수 있기 때문) 

중복호출 되는 n을 메모이제이션하여 알고리즘을 구현하면 원하는 결과를 얻을 수 있다.

 

다른 방법으로는 n이 1, 2, 3 일 때 방법의 수를 사전에 메모라이징 해두고 기저사례를 조금 수정하면 동일한 결과를 얻을 수 있다.


#include <iostream>
#include <cstring>
using namespace std;

int memo[11];

int Solution(int n)
{
	if (n == 0 || n == 1) return 1;

	int& ret = memo[n];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 1; i <= 3; i++)
		if (n - i >= 0) ret += Solution(n - i);
	
	return ret;
}

/*
int Solution2(int n)
{
	memo[1] = 1, memo[2] = 2, memo[3] = 4;

	if (n == 1 || n == 2 || n == 3) return memo[n];

	int& ret = memo[n];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 1; i <= 3; i++)
		ret += Solution(n - i);

	return ret;
}
*/
int main(void)
{
	memset(memo, -1, sizeof(memo));
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		cout << Solution(n) << endl;
	}
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 11726번: 2 x n 타일링  (0) 2020.06.08
백준 1003번: 피보나치 함수  (0) 2020.06.07
백준 1463번: 1로 만들기  (0) 2020.06.07
백준 1300번: K번째 수  (0) 2020.05.22
백준 2110번: 공유기 설치  (0) 2020.05.21

[문제 링크]

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net


알고리즘 문제해결전략에서 배운 방식으로 메모이제이션하여 Top-down 방식으로 풀었는데 무난하게 정답처리를 받을 수 있었다.

하지만 필자가 사용하는 컴파일러인 Visual Studio 2017 환경에서 돌렸을 때 N이 8000정도만 넘어가도 스택 오버플로가 발생하였다.

원인은 N이 커지면 커질수록 재귀호출 횟수가 급격하게 증가하는데, 이때 프로그램이 컴파일러의 호출 스택에서 이용가능한 공간 이상을 사용하려다 충돌이 일어나게 되는 것이었다.

 

따라서 스택 오버플로 문제를 해결하기 위해 재귀호출이 아닌 for문으로 알고리즘을 구현하였고, 재귀호출 없이 Top-down 방식을 구현하는 것은 불가능하다 판단하여 Bottom-up 방식으로 문제를 해결하였다.


#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int memo[1000001];

inline int min(int a, int b) { return a < b ? a : b; }

int TopDown(int N)
{
	if (N == 1) return 0;

	int& ret = memo[N];
	if (ret != -1) return ret;

	ret = 0;

	int A = INF, B = INF, C = INF;
	if (N % 3 == 0) A = 1 + TopDown(N / 3);
	if (N % 2 == 0) B = 1 + TopDown(N / 2);
	C = 1 + TopDown(N - 1);

	return ret = min(A, min(B, C));
}

int BottomUp(int N)
{
	memo[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		memo[i] = memo[i - 1] + 1;
		if (i % 3 == 0) memo[i] = min(memo[i], memo[i / 3] + 1);
		if (i % 2 == 0) memo[i] = min(memo[i], memo[i / 2] + 1);
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;
	
	memset(memo, -1, sizeof(memo));
	
	cout << BottomUp(N) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1003번: 피보나치 함수  (0) 2020.06.07
백준 9095번: 1, 2, 3 더하기  (0) 2020.06.07
백준 1300번: K번째 수  (0) 2020.05.22
백준 2110번: 공유기 설치  (0) 2020.05.21
백준 2512번: 예산  (0) 2020.05.20

[문제 링크]

 

1300번: K번째 수

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B��

www.acmicpc.net


https://jaimemin.tistory.com/988 꾸준함 님의 블로그를 참고해서 겨우 이해한 문제였다. 아직도 조금 헷갈리긴 한다.

 

arr[i][j] 에 해당하는 숫자는 i * j 이므로, i행은 i의 배수로 이루어져 있다. (ex. i * 1, i * 2, i * 3 .... i * N)

이를 바탕으로 어떤 임의의 숫자 M을 i가 1부터 N까지인 경우에 대해 M / i 한 몫을 cnt 변수에 누적시키면 M은 cnt+1 번째 수라는 사실을 알 수 있다.

이 때 주의해야 할 것이 만약 M / i 한 몫이 N보다 클 경우 배열의 최대 범위보다 큰 값을 누적하게 되므로 오답이 출력되기 때문에 M / i 한 몫을 누적하는 것이 아닌 배열의 최대 길이인 N을 누적시킨다.

 

전부 누적시켰다면 입력받은 K와 비교를 하여 만약 cnt가 K보다 작을 경우 더 큰 mid값을 탐색하기 위해 start = mid + 1 로 바꿔준다.

반대로 cnt가 K보다 크거나 같을 경우 result에 mid 값을 저장하고, 최적의 해를 찾기 위해 end = mid - 1 로 바꿔서 재탐색한다.

 

start가 end보다 커질 때까지 위 과정을 반복하면 result에는 N X N 배열에서 K번째 수에 해당하는 정수가 저장되게 된다.


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

int main(void)
{
	int N, K;
	cin >> N >> K;

	int start = 1, end = K, result;
	while (start <= end)
	{
		int mid = (start + end) / 2, cnt = 0;
		for (int i = 1; i <= N; i++)
			cnt += min(mid / i, N);
		if (cnt >= K)
		{
			result = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}
	cout << result;

	return 0;
}

알고리즘 200일 프로젝트 - 47 day

'알고리즘 > BOJ' 카테고리의 다른 글

백준 9095번: 1, 2, 3 더하기  (0) 2020.06.07
백준 1463번: 1로 만들기  (0) 2020.06.07
백준 2110번: 공유기 설치  (0) 2020.05.21
백준 2512번: 예산  (0) 2020.05.20
백준 1654번: 랜선 자르기  (0) 2020.05.20

+ Recent posts