[2021 acm-icpc] 6/30 연습 문제

1. 백준 3687번 - 성냥개비 (Gold 2 - dp, Greedy)

https://www.acmicpc.net/problem/3687

3687번: 성냥개비

 

풀이

 

0~9까지의 숫자는 아래와 같은 개수의 성냥개비로 이루어진다.

 

0 = 6개, 1 = 2개, 2 = 5개, 3 = 5개, 4 = 4개, 5 = 5개, 6 = 6개, 7 = 3개, 8 = 7개, 9 = 6개

 

이 때 n개의 성냥개비로 만들 수 있는 최대의 숫자는 반드시 "1" 또는 "7"으로만 이루어진다.

왜냐하면 최대의 숫자는 자릿수가 많은 것이 무조건 큰 숫자가 된다.

즉, 최소 개수의 성냥개비로 최대의 자릿수를 만들어내야 한다.

그렇기 때문에 만약 성냥개비가 짝수개라면 2개를 사용한 1을 계속해서 붙여넣으면 되고

성냥개비가 홀수개라면 맨 앞자리에 3개를 사용한 7을 놓고 나머지는 전부 1로 채워주면 된다.

 

그렇다면 최소의 숫자는 어떻게 구할까?

일단 성냥개비 2~7개 까지는 무조건 한자리수가 최소의 수가 될 것이다. 

 

	2	3	4	5	6	7
최소의 숫자	1	7	4	2	0, 6	8

이제 성냥개비를 8개 쓴다고 가정해보자.

경우의 수는 2+6, 3+5, 4+4 이 세가지 경우밖에 없다.

(이때 2+6이란 성냥개비 2개로 1을 만들고, 6개로 0(,6)을 만든다는 의미이다.)

그렇다면 결국 10, 55, 44 이 셋 중 최소값인 10이 dp값으로 저장된다.

 

위 과정을 통해 dp[2] ~ dp[8]까지의 값을 채워줄 수 있다.

 

다음부터는 완벽한 dp 알고리즘이다.

 

예를 들어 n = 15 라면

2 + 13, 3 + 12, ..., 7 + 8 의 경우의 수가 존재한다.

이때 dp[13], dp[12], dp[11], ... 은 앞의 과정에서 구했기 때문에 사용할 수 있다.

 

여기서 주의해야 할 점은 그럼 dp[6] + dp[9]를 하면 반드시 답이라고 할 수 있을까?

 

아니다.

물론 위의 경우(n = 15)에서는 답이 도출 되지만 이는 순전히 운이다.

왜냐하면 문제의 조건에서 "맨 앞 자리에만 0이 들어올 수 없다"고 하였기 때문이다.

즉 정답은 108인데 168로 도출 되는 경우가 생길 수 있다. 

 

따라서 2~8 까지는 다른 배열에 넣어놓고 사용하는 것이 좋다.

(물론 j = 6일때만 예외처리 해줘도 되지만 코드가 너무 더러워진다..)

  

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[107];
ll num[] = { 0,0,1,7,4,2,0,8,10 }; // num[6] = 0이고 dp[6] = 6임!!!

int main() {
	// max는 짝수일때는 2로 나눈 몫 만큼 1 찍어주기
	//       홀수일때는 맨 앞에 7 붙인 뒤 2로 나눈 몫 만큼 1 찍어주기
	// min은 dp 
	dp[2] = 1; dp[3] = 7; dp[4] = 4; dp[5] = 2; dp[6] = 6; dp[7] = 8, dp[8] = 10;
	for (int i = 9; i <= 100; i++) {
		ll temp = LLONG_MAX; // ll의 최대값
		for (int j = 2; j <= 7; j++) temp = min(temp, dp[i - j] * 10 + num[j]);
		dp[i] = temp;
	}
	int t, n;
	cin >> t;
	while (t--) {
		cin >> n;
		cout << dp[n] << " ";
		if (n <= 3) n == 2 ? cout << 1 : cout << 7;
		else {
			if (n % 2 == 1) cout << 7;
			for (int i = 0; i < (n / 2) - (n % 2); i++) cout << 1;
		}
		cout << "\n";
	}
}

 

 

2. SCPC 2020 2차 예선 1 - 실력 맞추기(DP, 누적합)

참고 블로그 : https://blog.shift.moe/2020/09/10/scpc-2020-round-2/

풀이

먼저 실력 차이의 최솟값을 찾아야하므로 A와 B를 먼저 정렬해야하는 것을 알 수 있습니다.

문제에서 A값을 최대 1번 바꿀 수 있는데, 값을 바꾸는 것은 무조건 B의 값에 맞게 바꿔야 A[i], B[j] 실력의 차가 0이 되니 이것이 제일 이득입니다.

 

규칙

A값을 바꿀 경우에는 경우의 수가 3가지가 생깁니다.

1) 값을 바꾸는 A의 위치가 그대로 일때(ex A[4] 값을 B[4]로 바꿀 때)

1-1) 위치 바꾸기 표

A[1]	A[2]	A[3]	A[4] = B[4]	A[5]	A[6]
B[1]	B[2]	B[3]	B[4]	B[5]	B[6]

1-2) 삭제 표

A[1]	A[2]	A[3]		A[5]	A[6]
B[1]	B[2]	B[3]		B[5]	B[6]

삭제 표에 남아있는 abs(A[i]-B[i])를 해주면 됩니다.

 

2) 값을 바꾸는 A의 위치가 왼쪽에 있을 때(ex A[4] 값을 B[2]로 바꿀 때) = B를 먼저 삭제 할 때

2-1) 위치 바꾸기 표

A[1]	A[4] = B[2]	A[2]	A[3]	A[5]	A[6]
B[1]	B[2]	B[3]	B[4]	B[5]	B[6]

2-2) 삭제 표

A[1]	A[2]	A[3]		A[5]	A[6]
A[1]		B[3]	B[4]	B[5]	B[6]

삭제표에 세로 줄로 값이 온전히 남아있는 A, B는 그대로 차이를 구해주고, 나머지는 ↖ 방향으로 A와 B의 차이를 구해주면 됩니다. -> abs(A[i-1] - B[i])

 

3) 값을 바꾸는 A의 위치가 오른쪽에 있을 때(ex A[3] 값을 B[5]로 바꿀 때) = A를 먼저 삭제할 때

3-1) 위치 바꾸기 표

A[1]	A[2]	A[4]	A[5]	A[3] = B[5]	A[6]
B[1]	B[2]	B[3]	B[4]	B[5]	B[6]

3-2) 삭제 표

A[1]	A[2]		A[4]	A[5]	A[6]
B[1]	B[2]	B[3]	B[4]		B[6]

삭제 표에 세로 줄로 값이 온전히 남아있는 A, B는 그대로 차이를 구해주고, 나머지는 ↙ 방향으로 A와 B의 차이를 구해주면 됩니다. -> abs(A[i] - B[i-1])

 

이렇게 해서 abs(A[i]-B[i])를 더해주는 누적합, abs(A[i-1]-B[i])를 해주는 누적합, abs(A[i]-B[i-1])을 해주는 누적합 총 3개의 누적합을 이용하여 문제를 풀어야하는 것을 알 수 있습니다.

 

왜 DP인가?

여기서 이제 DP가 쓰입니다. DP의 크기는 dp[N][2][2]로 첫 번째[2]는 A의 값을 삭제했는지 유무, 두 번째 [2]는 B의 값을 삭제했는지 유무입니다.

1. dp[i][0][0]

아무것도 삭제하지 않았으므로 dp[i][0][0] = dp[i-1][0][0] + abs(A[i] - B[i]) 

 

2. dp[i][1][0]

이번에 A를 삭제한 경우 dp[i-1][0][0]

이전에 A를 삭제한 경우(위의 3번 규칙) dp[i-1][1][0] + abs(A[i] - B[i-1])

따라서 dp[i][1][0] = min(dp[i-1][0][0], dp[i-1][1][0] + abs(A[i] - B[i-1]))

 

3. dp[i][0][1]

이번에 B를 삭제한 경우 dp[i-1][0][0]

이전에 B를 삭제한 경우(위의 2번 규칙) dp[i-1][0][1] + abs(A[i-1]-B[i])

따라서 dp[i][0][1] = min(dp[i-1][0][0], dp[i-1][0][1] + abs(A[i-1]-B[i]))

 

4. dp[i][1][1]

이미 A가 삭제된 상태에서 이제 B를 삭제하는 경우 dp[i-1][1][0]

이미 B가 삭제된 상태에서 이제 A를 삭제하는 경우 dp[i-1][0][1]

이미 A와 B가 삭제된 경우 dp[i-1][1][1] + abs(A[i]-B[i])

따라서 dp[i][1][1] = min({dp[i-1][1][0], dp[i-1][0][1], dp[i-1][1][1] + abs(A[i]-B[i])})

 

이것을 코드로 적어주면 아래와 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 2 * 1e5 + 2;
ll A[N], B[N], dp[N][2][2];
ll ans = 1e18;

int n;

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

	int t;
	cin >> t;
	for(int z = 1; z <= t; z++) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> A[i];
		for (int i = 1; i <= n; i++) cin >> B[i];
		sort(A + 1, A + n + 1);
		sort(B + 1, B + n + 1);
		dp[1][0][0] = abs(A[1] - B[1]);
		for (int i = 2; i <= n; i++) {
			dp[i][0][0] = dp[i - 1][0][0] + abs(A[i] - B[i]);
			dp[i][1][0] = min(dp[i - 1][0][0], dp[i - 1][1][0] + abs(A[i] - B[i - 1]));
			dp[i][0][1] = min(dp[i - 1][0][0], dp[i - 1][0][1] + abs(A[i - 1] - B[i]));
			dp[i][1][1] = min({ dp[i][1][0], dp[i][0][1], dp[i - 1][1][1] + abs(A[i] - B[i]) });
		}
        cout << "Case #" << z << endl;
		cout << min(dp[n][0][0], dp[n][1][1]) << endl;
	}
}

 

 

3. SCPC 2020 2차 예선 2번 문제 - 고구마

문제

 

서로 다른 가격이 매겨져 있는 고구마가 줄줄이 연결되어있는 경우, 최대 가치를 가지는 고구마 구간의 합을 구하시오.

 

풀이

 

문제는 상당히 간단합니다.

최대 가치의 구간만 찾으면 되는데, 문제는 입력으로 주어지는 구간의 길이 N이 최대 30만이라는 점입니다.

이 경우 누적합을 이용해 (i, j) = i ~ j 번째 인덱스 구간의 합을 O(1) 시간에 구할 수 있다하더라도, 모든 i, j 에 대해 구해줘야 하기 때문에 O(N^2) 시간이 걸려 시간초과가 나게 됩니다.

 

하지만, 우리는 어떤 인덱스 i에 대해 i 보다 큰 인덱스 중, 해답과 가장 가까운 (구간의 합이 m 이하이며, 가장 큰) 인덱스를 단번에 구할 수 있습니다. 

 

테스트케이스를 예로 들어 봅시다.

10 200

31 -41 59 26 -53 58 96 -93 -23 85

 

이 경우 부분합은 다음과 같습니다.

 

31 -10 49 75 22 80 176 83 60 145

 

만약 우리가 0번째 idx를 고정한다고 하면, 0번째가 i일 때 가장 최적의 j는 6입니다. 부분합이 176이므로 200을 넘지 않습니다.

만약 2번째 idx라면, 최적은 동일하게 6입니다. 이 때 부분합은 (176 - (-10)) 으로 186이므로 200을 넘지 않고, 정답이 됩니다.

 

이 방법은 lower_bound를 이용해 특정 수를 넘지 않는 최대값을 O(1) 시간에 구할 수 있으며,

이렇게 각 인덱스마다 작업을 반복한다면 시간복잡도는 O(N) 입니다.

 

단, lower_bound의 조건은 "모든 수가 정렬되어 있을 때" 를 가정합니다.

따라서 우리는 부분합을 set에 넣고 lower_bound를 하면, 매번 정렬하는 작업을 피할 수 있습니다. 시간복잡도는 동일합니다.

 

 

소스 코드(.cpp)

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

typedef long long ll;

ll psum[300010];
int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T, test_case;
	cin >> T;
    
	for(test_case = 0; test_case  < T; test_case++)
	{
	    memset(psum, 0, sizeof(psum));
        ll ans = 0;
		ll n, m;
		cin >> n >> m;
        
		set<ll>st;
        
		for (int i = 0; i < n; i++) {
			ll tmp; cin >> tmp;
			if(i == 0) psum[0] = tmp;
			else psum[i] = psum[i - 1] + tmp;
            
			st.insert(psum[i]);
            
            if(psum[i] <= m) ans = max(ans, psum[i]);
            
			auto psumj = st.lower_bound(psum[i] - m);
            
			if (psumj != st.end()) {
				ans = max(ans, psum[i] - *psumj);
			}
		}
		
		cout << "Case #" << test_case+1 << "\n";
		cout << ans << "\n";
	}

	return 0;
}