그리디 (2)

 

 

 

BOJ17420 깊콘이 넘쳐흘러

'특정일에 사용하기로 정한 기프티콘'이 '기한이 가장 적게 남은 기프티콘'이여야만 사용할 수 있을 때,

한 번 연장할 때 30일씩 연장되는 기프티콘을 모두 사용하기 위한 최소 연장 횟수를 구한다.

 

1. 계획한 사용일자가 적게 남은 순으로 기프티콘 정렬

2. 정렬된 기프티콘의 사용 기한이 증가수열이 되도록 연장

 2-1. 이때 사용일자가 같은 기프티콘이 있음에 주의

 

 

 

BOJ1898 이전 수열은 어떤 수열일까

1부터 N까지의 수를 나열한 수열 {Sn}이 주어질 때

모든 i(1≤i≤N)에 대해 | Si-Ai | < 2 인 수열 중

오름차순으로 나열할 때 가장 앞에 오는 수열 {An}을 찾는다.

 

N=8일 때, 4자리에는 3,4,5,가 배치될 수 있지만 8자리에는 7,8만 배치할 수 없음에 유의해서 규칙을 찾음

1. 본래 수열 {Sn}에서 숫자 1~N의 위치 저장

2. N와 N-1의 위치 비교

 2-1. N이 N-1보다 앞에 있다면 두 수의 위치를 바꾸고 N-2와 N-3의 위치 비교

 2-2. N-1이 N보다 앞에 있다면 N의 위치를 그대로 두고 N-1과 N-2의 위치 비교

 2-3. 뭐 1, 2부터 비교해도 됨

 

 

 

BOJ3366 수열 줄이기

이웃한 두 수를 두 수 중 큰 수 하나로 줄이는(reduce) 비용이 두 수 중 큰 값의 크기일 때

수열 a1,...,an의 길이를 1로 줄이기 위한 최소 비용을 구한다.

 

약간 행렬의 곱 연산 횟수같은 느낌도 났는데 우선순위 연산하듯 스택(S)/벡터(V)를 이용한다.

1. 숫자 a 입력

2. S.top()/V.back() ≤ a가 될 때까지 reduce연산

3. 종료 시 a를 S에 push/V에 push back

	if (!V.empty() && V.back() <= a) {
		while (V.back() <= a) {
			V.pop_back();
			
			if (V.empty()) { ans += a; break; }
			else ans += (V.back() < a) ? V.back() : a;
		}
	}
	V.push_back(a);

 

 

 

BOJ17842 버스 노선

버스 정류장과 정류장 간 도로가 트리 형태로 주어질 때

모든 도로에 적어도 1개 이상의 버스 노선이 지나도록 하는 버스 노선의 최소 개수를 구한다.

 

사실 온갖 dfs를 고민했었는데 이렇게 간단히 풀릴 줄은..

이웃한 정류장이 한 개뿐인 정류장 두 개를 종점으로 하는 버스 노선을 만들면 된다.

 

 

 

BOJ3687 성냥개비

주어진 성냥개비로 만들 수 있는 최대/최소 자연수를 구한다.

 

최대:

자릿수가 최대이기만 하면 되기 때문에 성냥개비가 2개밖에 쓰이지 않는 1을 최대한 이용하는 수를 구한다.

 

최소:

2부터 21까지는 규칙이 있으면서도 예외가 있어 값을 구해 배열에 저장해두었다.

22부터는 15부터 21까지의 수 뒤에 8을 붙일 수 있는 만큼 붙여주면 된다.