이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.

뭔가 했는데 알고리즘 분류를 보니 LIS라고 한다.

lower_bound로 최장증가수열을 구현하는 방식을 봤는데 실제로 유효한 수열을 구하진 않았다.

그런데 이 문제는 수열을 구하는 게 아니라 수열의 길이만 구하면 되므로 최대한 생략하고 수열의 길이만 구하도록 바꿨다.

1. 짝수 번 선택시 원래대로가 되기 때문에 같은 칸을 두 번 이상 선택할 필요가 없다.

2. 1번 조건을 다르게 생각해보면 선택 순서또한 중요치 않다는 뜻도 된다.

왼쪽 위부터 한자리씩 비교하며 다르면 그 칸을 포함해 오른쪽으로 3, 아래로 3 칸을 바꿔준다.

전체가 같아지면 멈추고 모든 칸을 다 바꿨는데 다르면 -1출력.

가장 큰 수를 구할 때

1. 앞자리에 9를 넣고 시작한다.

2. 다음 부등호가 “<” 라면 부등호 다음 수를 9로 만들고 그전의 자리에는 -1을 해준다.

3. “>” 라면 사용 안 했던 수 중에 가장 큰 수를 넣는다.
   이런 방식으로 부등호 개수만큼 반복한다.

딴 거 다 필요 없고 가장 싼 패키지와 낱개 가격만 있으면 된다.

그걸 구하기 위해 나는 정렬을 사용한 모양이다. 굳이 그랬어야 할까.

아무튼 경우의 수는 3가지다.

1. 패키지로 살 수 있을 만큼 산 후 나머지 부족한 것을 낱개로 구입.

2. 전부 낱개로 구입.

3. 기타줄 몇 개 남더라도 싹 다 패키지로 구입.

3개 중 가장 작은 게 답이다.

문제에 헷갈리는 문장이 있었다.

“다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.”

???????????

한참을 보다가 다음 줄 보고 이해했다.

“즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.”

ㅇㅎ

first는 어차피 오름차순으로 정렬되니 다음 사람의 점수보다 무조건 낮을 것이고 그 와중에 second까지 작으면 조건에 의해 걔는 탈락이다.

가장 작은 답이 나오려면 +끼리 괄호로 묶고 계산하면 된다. 라고 생각했지만 계속 반례가 생각나서 이건 아닐 거라고 판단했고 그냥 첫 번째 -가 나온 순간부터 다 빼버리면 처음 생각했던 것보다 단순하게 끝난다.

+아스키코드 10은 line feed (다음 줄)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
using namespace std;
int main()
{
	bool ch = false;
	int a, b;
	char c;
	scanf("%d", &a);
	for(;scanf("%c", &c), c != 10;)
	{
		if(c == '-') ch = true;
		scanf("%d", &b);
		if(ch) a -= b;
		else a += b;
	}
	cout << a;
}

단순 그리디. B 안에서의 차이가 가장 적은 A를 구하면 그게 답이다.

추가하는 연산은 무조건 차이가 가장 적게 할 테니까 신경 쓰지 않는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
using namespace std;
int main()
{
	char a[50], b[50];
	cin >> a >> b;
	int al = sprintf(a, "%s", a);
	int bl = sprintf(b, "%s", b);
	int c = 51;
	for(int i = 0; i < bl - al + 1; i++)
	{
		int co = 0;
		for(int j = 0; j < al; j++)
		{
			if(b[j+i] != a[j]) co++;
		}
		if(co < c) c = co;
	}
	cout << c;
}

지금보면 좀 한심한 코드다.

엄청 간단한 문제였는데 방심했다가 틀렸다.

• 여자 수 / 2
• 남자 수
• 여자 수 + 남자 수 - 인턴 수

3개 중에 가장 작은 값이 답이다. 가장 작은 값을 제외하곤 서로의 반례가 되기 때문.

1
2
3
4
5
6
7
8

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n, m, k;
    cin >> n >> m >> k;
    cout << min(min(n/2, m), (n+m-k)/3) << endl;
}

어떤 수가 3의 배수인지 확인하는 방법은 각 자릿수를 모두 더한 값이 3의 배수여야 한다. 이는 간단한 방법으로 증명할 수 있다. 10^n자릿수가 9일 때 3을 더하면 10^n의 자리에서 7만큼을 손해 보고 10^n+1의 자리에서 1의 이득을 본다. -7+1(역시나 3의 배수)

결국엔 계속 3의 배수가 되는데 생각해보니 정렬된 거나 안된 거나 같이 위의 조건을 만족한다면 그냥 모듈러 연산으로 해도 된다는 생각이 들었다. 어쨌든 30의 배수가 되려면 위의 조건에서 0이 문자열에 포함되어 있는지 확인해 봐야 한다.

조건을 모두 만족한 후 내림차순 정렬하면 풀린다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(char a, char b)
{
	return a > b;
}
int main()
{
    string n;
    cin >> n;
    long long s = 0;
    bool z = false;
    for(int i = 0; i < n.size(); i++)
    {
    	s += (n[i] - '0');
		if(!(n[i] - '0'))
        	z = true;
    }
    if(!z || s % 3)
    	cout << -1 << endl;
    else
    {
        sort(n.begin(), n.end(), cmp);
		cout << n << endl;
    }
}