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

문제량을 늘리고 나서 제법 여유롭게 순항하고있다.

방학의 힘은 생각보다 굉장하다는걸 온몸으로 느끼고 있는 요즈음.

잔디(덜연함)

#1 백준 2477 - 참외밭 ( S2 )

https://blog.koderpark.dev/328

백준 BOJ 2477 - 참외밭

많은_조건_분기 태그가 붙을거 같이 생긴 문제이지만,

의외로 그리 어렵지 않은 문제.

 

동서남북 방향을 나타내는 숫자가 들어오는 규칙을 잘 이용해서

문제를 해결할 수 있다.

 

편의상 앞으로 저 ㄴ, ㄱ 모양을 큰 사각형에서 작은 사각형이 "패인" 모양으로써 설명하겠다.

 

일단 지문에 대해 올바르게 이해하고 있다면 빠르게 떠올릴 수 있는 발상으로서,

입력이 한번만 들어온 방향이 큰 사각형의 가로세로 넓이가 됨을 떠올릴 수 있다.

 

이 가로세로 변의 길이를 저장해둔 뒤에, 남은 변들 중에서 어떤것이

안쪽의 작은 사각형인지를 판별해내야 하는데,

문제에서 주어진 입력 순서가 반시계 방향으로 일정하기 때문에,

작은 사각형에 포함되는 변들은 탐색 순서상

그 앞에 있는 변과 그 뒤에 있는 변 둘의 방향이 동일하다는것을

눈치챈다면 쉽게 해결해 줄 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<pair<int,int>> v;
int cnt[10] = {0};

vector<int> large;
vector<int> small;

int idx(int k){
	if(k<0) return k+6;
	return k%6;
}

int main(){
	int N;
	int a,b;
	
	int large = 1;
	int small = 1;
	
	cin >> N;
	
	for(int i=0; i<6; i++){
		cin >> a >> b;
		v.push_back({a,b});
		cnt[a]++;
	}
	
	for(int i=0; i<6; i++){
		if(v[idx(i-1)].x == v[idx(i+1)].x){
			small *= v[i].y;
		}
		else if(cnt[v[i].x] == 1){
			large *= v[i].y;
		}
	}
	
	cout << (large - small) * N;
	return 0;
}

처음에는 KOI 2018 <두 박스> 같은 문제인가 싶어서

손도 대기 싫었었는데

어찌저찌 깔끔하게 해결했던 문제.

---

#2 백준 17087 - 숨바꼭질 6 ( S2 )

수빈이가 동생들을 모두 찾고자 할때 한번에 이동할수 있는 이동거리 D의 최댓값을 구하는 문제.

https://blog.koderpark.dev/349

백준 BOJ 17087 - 숨바꼭질 6

각 동생들에 대해서 수빈이와의 거리 dir[i] 를 먼저 계산해 준 다음,

 

수빈이의 이동거리가 D일때 이동가능한 거리는 D, 2D, 3D, ... 이므로

dir[i] 가 D의 배수가 되는 수여야만 한다.

 

역으로 말해서,

모든 dir[i] 의 약수들 중에서

공통인 약수들만이 동생들을 모두 찾고자 할때 수빈이가 이동할수 있는 거리이고,

이러한 공약수 중의 최댓값인 최대공약수를 구하면 된다.

 

알고리즘으로는 유클리드 호제법을 활용했다.

구현이 극단적으로 간편하고 성능또한 뛰어나기 때문에

대부분의 상황에서 사용할 수 있으므로 외워두면 좋다.

 

int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

전체 소스코드는 아래에

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

vector<int> dir; // 수빈이로부터의 거리. 

int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(){
	int N,S,k;
	cin >> N >> S;
	for(int i=0; i<N; i++){
		cin >> k;
		dir.push_back(abs(S-k));
	}
	
	if(N == 1){
		cout << dir[0];
		return 0;
	}
	
	int ans = gcd(dir[0], dir[1]);
	for(int i=2; i<N; i++) ans = gcd(ans, dir[i]);
	cout << ans;
	return 0;
}

---

#3 백준 2564 - 경비원 ( S1 )

https://blog.koderpark.dev/336

백준 BOJ 2564 - 경비원

직사각형으로 주어져서 헷갈리기 쉬운 문제.

어차피 직사각형의 테두리를 따라서만 이동해야 하므로,

직사각형을 임의로 왜곡해서 원형으로 상상해도 좋다.

 

원형으로 그래프를 펼쳤다면 원 위의 아무런 한 점을 잡아서

해당 점으로부터 떨어진 거리들을 구해줄 수 있다.

이때 시계방향 거리 / 반시계방향 거리 둘을 섞어서 계산해주면

계산이 일괄적이지 못하게 되므로 한쪽 방향을 골라서 계산하는것을 추천한다.

 

모든 가게와 동근이의 위치에 대해서 떨어진 거리를 구해준 다음,

 

다시 원을 수직선상에 펼쳐놓고 생각했을때의

두 점 A,B 사이 거리를 ABS(A-B)를 구하고

반대방향으로 도는 경우에 대해서도 이와 비슷하게 처리해주면

정답을 얻을 수 있다.

 

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

int dis[123] = {0};
int pdis = 0;

int main(){
	int R,C,N;
	int a,b;
	
	cin >> R >> C;
	cin >> N;
	
	for(int i=0; i<=N; i++){
		cin >> a >> b;
		if(a == 1) dis[i] = b;
		if(a == 2) dis[i] = 2*R+C-b;
		if(a == 3) dis[i] = 2*(R+C)-b;
		if(a == 4) dis[i] = R+b;
	}
	
	int ans = 0;
	int tmp = 0;
	
	for(int i=0; i<N; i++){
		tmp = abs(dis[i] - dis[N]);
		ans += min(2*(R+C) - tmp, tmp);
	}
	cout << ans;
	return 0;
}

 

첨언

지난번에 티어 올린다고 해놓고 티어가 하나도 안올라간거같다면

기분탓이 아니다 ㅠㅠ

 

태그를 알고 푼다던지 푼 사람이 많은 야무진 문제들은 어찌저찌 푼다지만

골드 랜덤디펜스를 당장 돌리기에는 좀 어려움이 있는듯 해서

G5~G4 정도에 좀 익숙해지는것부터 해야할거같다...