알고리즘 2인 스터디 #1주차 - 박성훈

방학동안에 내실 더 튼튼하게 다지려고 시작한

백준 랜덤디펜스

학기중에는 실버5~실버1 선에서 진행했었는데

종강후 푸는 문제들의 난이도를 좀 더 올려보고자 한다.

풀이 연하게만 자라고 있는 나의 잔디밭....

스트릭 유지하기 위한 하루 1문제가 아니라

문제량 조금씩 늘려서 하루 3문제에 적응하고 있는데

이를 백랜디(백준 랜덤디펜스) 가 아니라 새로

여기서 아이디어 착안한거 맞다

"매삼백" 으로 명명하도록 하겠다 히히

아무튼 개강 전까지 "매삼백"을 유지해보는게 목표.

 

푸는 문제량이 문제량인만큼 야무진 문제 몇문제만 간추려서 소개하고자 한다.

 

#1 백준 12869번 - 뮤탈리스크 ( G4 )

https://blog.koderpark.dev/315

백준 BOJ 12869 - 뮤탈리스크

 

처음에는 9, 3 두 수 모두 최소단위에 해당하는 1의 배수임에서 착안,

boj 5585 거스름돈 등의 문제와 같이 배수관계가 성립하고 있기 때문에

그리디 알고리즘인가 라고 생각하면서 문제에 접근했다.

 

그러나 그리디 풀이의 반례가 존재했었고, 입력 범위가 별로 크지 않다는 생각에 DP를 적용해서

두번째 시도를 해보았다.

dp[a][b][c] : scv 셋의 체력을 각각 a,b,c로 만들기 위해 공격해야 하는 횟수의 최솟값.

이렇게 dp 테이블을 정의한다면 dp[0][0][0]이 답이 될 것이고,

 

dp[a][b][c] 상태에서 뮤탈리스크가 공격할 수 있는 경우의 수는 3! = 6가지이다.

여섯가지 모두에 대해서 재귀함수 or DFS 를 적용해서 문제를 해결해주면 된다.

 

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

int dp[99][99][99];

int find(int a, int b, int c){
	a = max(a,0);
	b = max(b,0);
	c = max(c,0);
	
	if(dp[a][b][c] != -1) return dp[a][b][c];
	
	return dp[a][b][c] = min({
		find(a-9,b-3,c-1)+1,
		find(a-9,b-1,c-3)+1,
		find(a-3,b-9,c-1)+1,
		find(a-3,b-1,c-9)+1,
		find(a-1,b-3,c-9)+1,
		find(a-1,b-9,c-3)+1
	});
}

int main(){
	memset(dp, -1, sizeof(dp));
	dp[0][0][0] = 0;
	
	int N,arr[3] = {0};
	
	cin >> N;
	for(int i=0; i<N; i++) cin >> arr[i];
	
	cout << find(arr[0],arr[1],arr[2]);
	return 0;
}

 

#2 백준 3049 - 다각형의 대각선 ( S5 )

https://blog.koderpark.dev/317

백준 BOJ 3049 - 다각형의 대각선

세 대각선이 한 점에서 만나지 않는 볼록 N각형에서의 교차점 갯수를 세는 문제.

 

교차점은 두개 이상의 대각선이 한 점에서 서로 만나는 경우에 만들어지는데,

세 대각선이 한 점에서 만나지 않는

조건 때문에 반드시 두개의 대각선 사이에서만 만들어질 수 있고,

볼록 N각형에서의 두개의 대각선 쌍의 갯수를 세는 문제 로 치환해서 생각해볼 수 있다.

이때

볼록 N각형

이라는 조건 때문에 꼭짓점 네개를 선택해 선분 두개를 만들때

두 선분이 교차하려면 반드시 X자 모양을 그려야 하고,

N각형에서 꼭짓점 4개를 선택하는 경우의 수 로 치환해서 생각해볼 수 있다.

 

즉, N개 중 4개를 순서상관없이 선택하는 NC4를 계산하는게 정답.

nCr의 계산에는 동적계획법을 사용했다.

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

ll dp[123][123] = {0};

int nCr(int n, int r){
	if(!n) return 0;
	if(!r) return 1;
	if(n == r) return 1;
	
	if(dp[n][r] != 0) return dp[n][r];
	
	return dp[n][r] = nCr(n-1,r-1) + nCr(n-1,r);
}

int main(){
	int N;
	cin >> N;
	
	ll spot = nCr(N,4);
	
	cout << spot;
	return 0;
}

 

#3 백준 3078 - 좋은 친구 ( G4 )

https://blog.koderpark.dev/324

백준 BOJ 3078 - 좋은 친구

등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구들의 쌍 갯수를 세는 문제.

브루트포싱 풀이는 O(KN) 으로 시간초과를 받게 되기 때문에,

슬라이딩 윈도우, 스위핑 등의 다양한 이름으로 불리는 테크닉을 통해서 문제를 해결해 줄 수 있다.

 

stdu[k]를 구간 (l,r] 내에 있는 이름의 길이가 K 인 학생들의 수 로 정하고

슬라이딩 윈도우 알고리즘 + 투 포인터 알고리즘 조합으로 이를 구해주면

정답을 구할 수 있는데,

 

stdu[k] 안에 자기 자신이 포함되어있는것과

좋은친구를 세는 경우가 두번 중복되기 때문에 답을 2로 나눠줘야한다는것

두가지에 유의해주면 된다.

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

int stdu[25] = {0};
string arr[345678];

int main(){
	int N,K;
	cin >> N >> K;
	
	for(int i=1; i<=N; i++){
		cin >> arr[i];
	}
	
	int l,r;
	ll ans = 0;
	
	for(int i=1; i<1+K; i++){
		stdu[arr[i].length()]++;
	}
	
	for(int i=1; i<=N; i++){
		l = max(0,i-K-1);
		r = min(N+1,i+K);
		
		stdu[arr[r].length()]++;
		stdu[arr[l].length()]--;
		
		//printf("[%s %d]", arr[i].c_str(), stdu[arr[i].length()]);
		
		ans += stdu[arr[i].length()]-1;
	}
	
	cout << ans/2;
	return 0;
}

 

첨언

입시한다고 백준안풀다가 대학와서 재활하니까 죽을맛이다 ㅠㅠ

살려주세요