굳건하게

문제 : https://www.acmicpc.net/problem/1006

[ 코멘트 ]

 처음에는 DP 말고 Set-cover Problem의 관점에서 습격자 초라기를 바라봤다.

 백준 예제 입력 1번을 가지고 다뤄보면,

  8 100

  70(1) 60(2)  55(3)   43(4)   57(5)  60(6)   44(7)   50(8)

  58(9) 40(10) 47(11) 90(12) 45(13) 52(14) 80(15) 40(16)

  총 16개의 구역이 존재하고, 한 소대가 최대 100명을 처리할 수 있다.

 이때, 한 번에 두 구역을 커버 가능한 경우를 모두 뽑아보면 다음과 같다.

 { 2, 10 }, { 3, 4 }, { 4, 5 }, { 7, 8 }, { 8, 16 }, { 9, 10 }, { 10, 11 }, { 13, 14 }, { 9, 16 } 이고

 여기에서 선택받지 못한 { 1 }, { 6 }, { 12 }, { 15 } 는 무조건 하나의 특수 소대가 커버해야 한다.

 따라서 이 문제를 집합 U = { 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16 } 를

 S = { { 2, 10 }, { 3, 4 }, { 4, 5 }, { 7, 8 }, { 8, 16 }, { 9, 10 }, { 10, 11 }, { 13, 14 }, { 9, 16 } } 에서

 최소 개수의 원소들을 뽑아서 집합 U를 만드는 문제로 바라보려 했다.

 하지만, 이런 Set-cover Problem은 NP hard Problem으로 항상 최적의 해를 구하는 알고리즘이 없어서,,, 포기했다,,,,

 그 후, DP 배열을 아무리 생각해도 아이디어가 떠오르지 않아 DP 배열 정의만 포스팅을 참고해 문제를 풀고 다른 분들 코드랑 비교해보는 시간을 가졌다...! ( 언제쯤 혼자서 이 정도 문제를 풀 수 있을까... )

[ 알고리즘풀이 ]

정의 )

 Enemy[2][N] := Enemy[0][N] 은 바깥쪽 구역, Enemy[1][N] 은 안쪽 구역의 적의 수입니다.

 DP[0][N] := 바깥쪽구역 1 ~ N, 안쪽구역 1 ~ N - 1 을 커버하는데 필요한 최소 특수 부대의 수.

 DP[1][N] := 바깥쪽구역 1 ~ N - 1, 안쪽구역 1 ~ N 을 커버하는데 필요한 최소 특수 부대의 수.

 DP[2][N] := 바깥쪽구역 1 ~ N, 안쪽구역 1 ~ N 을 커버하는데 필요한 최소 특수 부대의 수.

점화식 )

 DP[0][N] =  min(dp[1][N - 1] + outer, dp[2][N - 1] + 1, );

 DP[1][N] = min(dp[0][N - 1] + inner, dp[2][N - 1] + 1, );
 DP[2][N] = min({ dp[0][N] + 1, dp[1][N] + 1, dp[2][N - 1] + horizon, , dp[2][N - 2] + outer + inner });

 그림으로 위의 점화식을 자세히 이해해보겠습니다.

1) DP[0][N]

DP[0][5] 는 아래와 같은 2가지 경우 중에 하나로 값을 찾을 수 있습니다.

 DP[1][4] 에서 Out4랑 Out5를 커버하는데 필요한 특수 소대의 수(Outer) 를 더한 값이랑,

 DP[2][4] 에서 Out5를 커버하는 특수 소대의 수(1) 을 더한 값 중 작은 값이 됩니다.

 즉, 다음과 같은 점화식을 얻을 수 있습니다.

 DP[0][N] =  min(dp[1][N - 1] + outer, dp[2][N - 1] + 1, );

2) DP[1][N]

 DP[1][5] 은 아래와 같은 2가지 경우 중에 하나로 값을 찾을 수 있습니다.

 즉, 다음과 같은 점화식을 얻을 수 있습니다.

 DP[1][N] = min(dp[0][N - 1] + inner, dp[2][N - 1] + 1, ); 

3) DP[2][N]

 DP[2][5] 는 아래와 같은 4가지 경우 중에 하나로 답을 찾을 수 있습니다.

 위에서 DP[0][5], DP[1][5] 의 값을 먼저 구했으므로, 그 값들을 이용해서 DP[2][5] 를 채울 수 있습니다.

 따라서, 다음과 같은 점화식이 성립합니다.

 DP[2][N] = min({ dp[0][N] + 1, dp[1][N] + 1, dp[2][N - 1] + horizon, , dp[2][N - 2] + outer + inner });

 하지만, 이렇게 DP 배열을 채워나가면 원형으로 이어져있다는 점을 고려하지 못하기 때문에, Out[1] 과 Out[N]을 동시에 커버할 수 있는 경우, In[1]과 In[N]을 동시에 커버할 수 있는 경우, Out[1] 과 Out[N] / In[1]과 In[N]을 동시에 커버할 수 있는 경우에 대해서도 초기값을 다르게 해서 DP 배열을 채우고 총 4가지 경우에 대해서 가장 작은 값을 답으로 출력하면 됩니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 987654321

using namespace std;

int dp[3][10001], N, W, enemy[2][10001];

void solve(void) { // 그냥 점화식대로 DP배열을 채우는 함수.
	for (int i = 2; i <= N; i++) {
		int outer = 2 - (enemy[0][i] + enemy[0][i - 1] <= W);
		int inner = 2 - (enemy[1][i] + enemy[1][i - 1] <= W);
		int horizon = 2 - (enemy[0][i] + enemy[1][i] <= W);

		dp[0][i] = min(dp[2][i - 1] + 1, dp[1][i - 1] + outer);
		dp[1][i] = min(dp[2][i - 1] + 1, dp[0][i - 1] + inner);
		dp[2][i] = min({ dp[2][i - 1] + horizon, dp[0][i] + 1, dp[1][i] + 1, dp[2][i - 2] + outer + inner });
	}
	return;
}

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

	int T;
	cin >> T;
	while (T--) {
		cin >> N >> W;
		for (int i = 0; i < 2; i++)
			for (int j = 1; j <= N; j++)
				cin >> enemy[i][j];

		if (N == 1) {
			cout << 2 - (enemy[0][1] + enemy[1][1] <= W) << '\n';
			continue;
		}

		int ans = INF;
		memset(dp, 0, sizeof(dp));

		dp[0][1] = dp[1][1] = 1; 
		dp[2][1] = 2 - (enemy[0][1] + enemy[1][1] <= W);
		solve();

		ans = min(ans, dp[2][N]);
		if (enemy[0][N] + enemy[0][1] <= W) {
			dp[2][0] = INF; dp[0][1] = 1; dp[1][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[1][N]);
		}

		if (enemy[1][N] + enemy[1][1] <= W) {
			dp[2][0] = INF; dp[1][1] = 1; dp[0][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[0][N]);
		}

		if (enemy[0][N] + enemy[0][1] <= W && enemy[1][N] + enemy[1][1] <= W) {
			dp[2][0] = INF; dp[0][1] = dp[1][1] = INF; dp[2][1] = 2;
			solve();
			ans = min(ans, dp[2][N - 1]);
		}

		cout << ans << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/1126

[ 코멘트 ]

1. DP 배열 정의가 도저히 생각나지않아, 구글링을 통해 DP 배열 정의만 참고함.

2. dp 배열을 -1로 초기화해야됨. 0으로 초기화해도 충분할 줄 알았지만, 0으로 초기화하면 새로운 막대만 사용하는 경우를 처리해줄 수가 없다. 따라서 -1로 초기화하고 dp[0][0] = 0, dp[0][top[0]] = top[0] 으로 초기값을 설정해야한다.

3. 

    if (dp[N - 1][0] == 0) 
        cout << -1;
    else 
        cout << dp[N - 1][0];

 위의 코드와 아래 코드는 다르게 작동한다... 이 부분 때문에 4시간은 날린 것 같다,,,

    cout << dp[N - 1][0] ? dp[N - 1][0] : -1;

 삼항 연산자를 사용하면 '?' 보다 출력 ' << ' 가 우선순위가 높기 때문에 dp[N - 1][0] 이 0이면 '-1'이 아니라 그냥 boolean 값 false가 출력된다.

[ 알고리즘풀이 ]

DP[ I ][ J ] = 0 ~ (i - 1)번 째 블록까지 사용해 두 개의 탑을 만들었고, 두 탑의 차이가 j일 때 큰 탑의 최대 높이.

DP 배열 정의부터 복잡하니 그림으로 이해해보자.

DP[ i - 1 ] [ J ] = K 라고 하자.

 그럼 0 ~ (i - 2)번 블록까지 사용해 위의 그림과 같은 상황이 만들어진 것이다.

 여기서 우리가 ( i - 1 )번 블록을 가지고 취할 수 있는 행동은 총 3가지다.

- 위의 상태를 그대로 둔다.

- (i - 1)번 블록을 왼쪽 더 높은 탑에다가 쌓는다. 그러면, 높이 차이랑 길이가 (i - 1)번 블록 길이 만큼 커진다.

- (i - 1)번 블록을 오른쪽 탑에다가 쌓는다.

 이때, 높이 차이 J 보다 (i - 1)번 블록이 크다면 오른쪽 탑이 더 높아지고 아니라면 여전히 왼쪽 탑이 더 높으므로 경우의 수를 나눠줘야한다.

			// 그대로두자 --> 변화없음.
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			// 탑의 큰 쪽에 쌓자. --> 차이가 j + top[i],  큰 탑이 dp[i - 1][j] + top[i];
			dp[i][j + top[i]] = max(dp[i][j + top[i]], dp[i - 1][j] + top[i]);
			// 탑의 작은 쪽에 쌓자. --> 경우의 수가 2가지.
			if (j < top[i]) // 탑의 최대가 바뀐다.
				dp[i][top[i] - j] = max(dp[i][top[i] - j], dp[i - 1][j] - j + top[i]);
			if (j >= top[i]) // 큰쪽이 계속 크다.
				dp[i][j - top[i]] = max(dp[i][j - top[i]], dp[i - 1][j]);

 위와 같은 점화식이 성립하고, 만약에 DP[ i - 1 ][ j ] 가 -1 이라면 애초에 조건을 만족하는 두 개의 탑이 존재하지 않으므로, 그냥 넘어간다.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int N, top[50], sum = 0;
int dp[50][500001]; // dp[i][j] : i번 째 조각까지 사용하고 두 탑의 높이 차가 j일 때, 큰 탑 높이의 최대값.

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> top[i];
		sum += top[i];
	}

	memset(dp, -1, sizeof(dp));

	dp[0][0] = 0;
	dp[0][top[0]] = top[0];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= sum; j++) {
			if (dp[i - 1][j] == -1)
				continue;
			// 쌓지말자 --> 변화없음.
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			// 탑의 큰 쪽에 쌓자. --> 차이가 j + top[i],  큰 탑이 dp[i - 1][j] + top[i];
			dp[i][j + top[i]] = max(dp[i][j + top[i]], dp[i - 1][j] + top[i]);
			// 탑의 작은 쪽에 쌓자. --> 경우의 수가 2가지.
			if (j < top[i]) // 탑의 최대가 바뀐다.
				dp[i][top[i] - j] = max(dp[i][top[i] - j], dp[i - 1][j] - j + top[i]);
			if (j >= top[i]) // 큰쪽이 계속 크다.
				dp[i][j - top[i]] = max(dp[i][j - top[i]], dp[i - 1][j]);
		}
	}
	dp[N - 1][0] ? cout << dp[N - 1][0] : cout << -1;
	return 0;
}

내 6시간,,,

문제 : https://www.acmicpc.net/problem/16434

[ 알고리즘풀이 ] - 단순구현

● 문제가 복잡해보이지만 읽어보면, 그냥 userHP를 최소 몇으로 시작해야 던전을 통과할 수 있을까! 하는 문제다.
● 단순하게 userHP = 0 으로 시작해서 던전을 통과하며 몬스터를 만나면 체력을 깎고, 포션을 만나면 최소 HP를 구해야 되므로 현재 깎인 체력(음수값) 보다 큰 값을 회복시켜줄 수 있어도 최소한으로(userHP = 0으로) 회복을 시켜가며 던전을 통과한다.
● 이때, 던전을 통과하며 가지게 되는 가장 작은 체력 값이 최소한으로 필요한 값이므로 양수로 부호를 변환해 초기 체력 1 을 더해주고 답을 출력해주면 된다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, t, a, h;
	long long userATK, userHP = 0, minValue = 999999999;

	cin >> N >> userATK;

	for (int i = 0; i < N; i++) {
		cin >> t >> a >> h;
		if (t == 1) {
			if (h % userATK == 0)
				userHP -= a * (h / userATK - 1);
			else
				userHP -= a * (h / userATK);
		}
		else {
			userATK += a;
			if (userHP + h >= 0)
				userHP = 0;
			else
				userHP += h;
		}
		minValue = min(minValue, userHP);
	}
	cout << -minValue + 1;
}

안녕하세요, 여행벌입니다.

오늘은 자바 연산자 중 단항 연산자들에 대해서 다뤄보겠습니다.

단항 연산자

 단항 연산자는 피연산자가 하나인 연산자로 이항 연산자에 비해 그 수가 적습니다.

부호 연산자 : +, -

 +, - 는 이항 연산자로 사용되면 덧셈과 뺄셈에 사용되지만, 단항 연산자로 수학에서와 동일한 의미를 갖습니다. 이때, 자바는 기본적으로 정수형 연산을 int 형으로 진행하고 그 결과도 int 형으로 반환하고, 실수형 연산을 double형으로 진행하고 그 결과도 double 형으로 반환하므로 부호 연산자를 사용할 때도 이 점을 주의해야 합니다.

예시 1)

package Hello;

public class HelloWorld {
	public static void main(String args[]) {
		int num = 5;
		System.out.println(-num);
	}
}

-5

 위의 코드는 부호 연산자 - 를 이용해 num 의 부호를 바꿔서 출력했습니다.

package Hello;

public class HelloWorld {
	public static void main(String args[]) {
		short num = 5;
		short num2 = -num;
	}
}

 위의 코드를 실행하면 num2 에는 -5가 저장될까요? 정답은 -num 은 int 형이지만 num2 는 short 형이므로 에러가 발생합니다.

증가 및 감소 연산자 : ++,  --

 증가 및 감소 연산자 ++, -- 는 피연산자의 앞부분에 붙이냐, 뒷부분에 붙이냐에 따라 작동하는 방식이 조금 다릅니다. 기본적으로 값이 하나 증가 및 감소하는 것은 동일하나 반영되는 시점에 차이가 있습니다. Prefix 방식은 연산으로 인한 값의 증가 및 감소가 연산이 진행된 문장에서 발생하고, Postfix 방법은 그다음 문장으로 넘어가야 반영이 됩니다.

예시 2)

package Hello;

public class HelloWorld {
	public static void main(String args[]) {
		int num1 = 5, num2 = 5;
		System.out.println("num1++ : " + num1++ + ' ' + "++num2 : " + ++num2);
		System.out.println("num1-- : " + num1-- + ' ' + "--num2 : " + --num2);
	}
}

num1++ : 5 ++num2 : 6
num1-- : 6 --num2 : 5

 결국 모든 코드를 수행하고 나서 num1, num2 에 모두 5가 저장되지만 적용되는 시점에 따라 출력되는 값이 다른 것을 확인할 수 있습니다.