[이코테] 실전 문제

DP 문제는 수식을 생각해 줘야하는데 어려운 문제에서는 그게 참 어렵다. 책의 실전 문제에서는 아직 엄청나게 어려운 문제는 없었다.

 

1로 만들기

주어진 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제였다.

 

연산 종류

• X%5 == 0 이면 5로 나누기
• X%3 == 0 이면 3으로 나누기
• X%2 ==0 이면 2로 나누기
• X - 1 하기

 

DP 문제를 풀 때는 초깃값을 설정할 수 있는 것은 설정하고, 나머지는 가장 큰 값으로 채우거나 비워놓아야 한다. 이 문제에서는 1,2,3,5 index의 값을 1로 설정할 수 있다.

 

문제의 수식은 4번째 값을 구할 때 찾아낼 수 있다.

dp[4] = min(dp[4-1]+1 , dp[4/2]+1)

연산을 할 수 있다면 dp[연산 결과]+1을 비교해 최솟값을 찾아내는 수식을 만들 수 있다.

dp[i] = min( dp[i-1]+1,  dp[i/2]+1,  dp[i/3]+1,  dp[i/5]+1 )
이 때, min 안에 들어가는 비굣값들은 연산할 수 있는 값들이다. (나눠떨어지거나 -1이거나)

int main() {
	
	int X;
	int i;
	int small;

	scanf("%d", &X);

	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 1;
	dp[5] = 1;

	for (i = 4; i <= X; i++) {
		small = 30001;
		if (i % 5 == 0) {
			small = min(small, dp[i / 5] + 1);
		}
		if (i % 3 == 0) {
			small = min(small, dp[i / 3] + 1);
		}
		if (i % 2 == 0) {
			small = min(small, dp[i / 2] + 1);
		}
		small = min(small, dp[i - 1] + 1);
		dp[i] = small;		
	}
	printf("%d", dp[X]);
}

/*
26
*/

 

---

개미 전사

N개의 식량이 주어지면 얻을 수 있는 식량의 최댓값을 구하는 문제이다. 이 문제는 개인적으로 앞의 문제보다 쉬웠는데 난이도는 반 칸 더 높았다.

 

문제의 조건은 이렇다.

• 최소 한 칸 이상 떨어진 식량창고를 약탈할 수 있다.

 

조건을 통해 첫 번째 칸과 두 번째 칸의 dp 초깃값을 정해야 한다는 것을 알 수 있다. 초깃값은 각각의 식량창고 값이다. 이 문제도 위의 문제와 같이 3번째 칸의 dp 값을 구하면서 수식을 생각해낼 수 있다.

 

dp[3] = min( dp[1]+arr[3],  dp[2] )

현재 dp 값은 한 칸 이상 떨어져야 하기 때문에 전전 칸의 dp 값과 현재 칸의 값을 더한 값과 전칸의 dp 값 중 더 작은 값이다. 수식으로 정리하면 아래와 같아진다.

dp[i] = min( dp[i-1],  dp[i-2]+arr[i] )

int max(int a, int b) {
	if (a < b) return b;
	return a;
}


int main() {
	
	int N;
	int arr[1001], dp[1001];
	int i;

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	dp[0] = arr[0];
	dp[1] = max(dp[0], arr[1]);
	//dp[2] = max(dp[0] + arr[2], dp[1]);

	for (i = 2; i < N; i++) {
		dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
	}

	printf("%d", dp[N - 1]);
	
}

/*
4 
1 3 1 5
*/

 

---

바닥 공사

이 문제는 처음 풀어보는 유형이고, 어릴 때부터 어려워했던 유형(도형 채우기..)이라서 어려웠다. 하지만 이 문제를 풀어봐서 앞으로는 같은 유형을 쉽게 풀 수 있을 것 같다.

 

가로 N, 세로 2인 바닥을 1x2, 2x1, 2x2 인 타일로 채우는 모든 경우의 수를 구하는 문제였다. 1<=N<=1000 인 값이 입력되고, 출력값은 796796으로 나눈 나머지를 출력해야 한다.

 

문제를 풀 때 왼쪽부터 차례로 바닥을 채운다고 생각하고 그림을 그려서 풀면 쉽게 수식을 생각해낼 수 있다.

 

문제의 타일의 가로 길이는 1인 경우와 2인 경우 2가지이기 때문에 초깃값은 N이 1인 경우와 2인 경우다. 가로 길이가 2가지여서 각각 왼쪽부터 채울 때 i-1 인 경우와 i-2인 경우로 나눠서 생각할 수 있다. 이때 주어진 타일의 가로 길이가 2인 경우는 1x2, 2x2 2가지가 있기 때문에 i-2인 경우는 2개가 있다.

 

이번 문제는 모든 경우의 수를 구하는 문제로 비교 후 최솟값이나 최댓값으로 dp 값을 설정하는 것이 아니고 단순히 앞의 값을 계속해서 더해나가면 된다.

 

여기까지 생각한 후 N이 3인 경우를 구해보면 수식을 얻을 수 있다.

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

dp[i] =  dp[i-1]  +  dp[i-2] x 2

int max(int a, int b) {
	if (a < b) return b;
	return a;
}


int main() {
	
	int N;
	int dp[1001];
	int i;

	scanf("%d", &N);

	dp[1] = 1;
	dp[2] = 3;
	//dp[3] = dp[2] + dp[1] * 2;

	for (i = 3; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] * 2 % 796796;
	}
	printf("%d", dp[N]);
}

/*
3
*/

 

---

효율적인 화폐 구성

첫 번째 문제와 거의 같은 문제였다. 다른 점은 나눠떨어지는 수를 입력받는다는 것이다.

 

N개의 화폐 단위를 입력받고 이 단위의 최소한의 화폐 개수로 M을 만드는 문제로 만들 수 없다면 -1을, 만들 수 있다면 최솟값을 출력하는 문제다.

 

먼저 dp 값들을 최댓값(문제에서 화폐 가치의 최대가 10000이라고 했으니 10001로 정할 수 있다.)으로 초기화 해준다. 그리고 입력받은 화폐 단위들을 dp 초깃값의 index로 하고 dp[coin[]]을 1로 정하면 된다. (2원이 있을 경우 dp[2]는 1, 화폐 1개로  2원을 만들 수 있다.) coin의 최솟값부터 M까지, N개의 단위로 나눠떨어지는 경우 min을 비교해주며 구할 수 있다.

 

이 문제 또한 직접 대입해보면 수식을 생각해내기 쉽다.

2,3 일 경우
dp[1] = MAX
dp[2] = 1
dp[3] = 1
dp[4] = min( dp[4] , dp[4-2] + 1 , dp[4-3] + 1) = min( MAX, 2, MAX ) = 2
dp[5] = min( dp[5] , dp[5-2] +1 , dp[5-3] +1) = min( MAX, 2, 2 ) = 2

dp[i] = min( dp[i] , dp[i-coin[0]]+1, dp[i-coin[1]]+1, ... , dp[i-coin[j]]+1)

#define MAX 10001

int coin[101];
int dp[101];
int N, M;

int min(int a, int b) {
	if (a > b) return b;
	return a;
}

int findMin(int num) {
	int i;
	int small=dp[num];

	for (i = 0; i < N; i++) {
		if (num - coin[i] > 0) {
			small = min(dp[num - coin[i]]+1, small);
		}
	}
	return small;
}

int main() {
	int i;


	scanf("%d %d", &N, &M);

	for (i = 1; i <= M; i++) {
		dp[i] = MAX;
	}

	//3원 종류가 있으면 dp[3]은 1개로 만들 수 있음
	for (i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
		dp[coin[i]] = 1;
	}

	sort(coin, coin + N);

	for (i = coin[0]; i <= M; i++) {
		dp[i] = findMin(i);
		//printf("dp[%d]: %d\n", i, dp[i]);
	}

	if (dp[M] == MAX) printf("-1");
	else printf("%d", dp[M]);
}

/*
2 15 
2 
3

3 4 
3 
5 
7
*/

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24