[BOJ] 2023 11월 3주차 정리

2023년 11월 13일 (월)  ~ 11월 19일 (일) - 푼 문제 (8 solved)

 
문제 링크: https://www.acmicpc.net/problem/13224

13224번: Chop Cup

---

 

13324번 Chop Cup (2023-11-13 기준 Bronze II)

 
단순하게 swap 해주면 되는 문제. 사실 이 날에는 문제 풀기 귀찮아서 브론즈 풀었다..
 

	c = [1,0,0]
	for i in input():
	if i == 'A':
	c[0], c[1] = c[1], c[0]
	elif i == 'B':
	c[1], c[2] = c[2], c[1]
	else:
	c[0], c[2] = c[2], c[0]
	print(c.index(1)+1)

view raw 13224.py hosted with ❤ by GitHub

---

 
문제 링크: https://www.acmicpc.net/problem/3749

3749번: Build Your Home

---

 

3749번 Build Your Home (2023-11-14 기준 Gold V)

 
다각형의 넓이를 구하는 문제. 흔히 고등학교 때 배웠던 신발끈 공식을 이용했다.
원래는 Python으로 구현을 했는데 계속 IndexError가 떠서 정규 표현식으로 whitespace를 다 지웠는데도 안되어서 그냥 C++로 구현했다.
 

	#include <bits/stdc++.h>
	#define fastio cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
	typedef long double ld;
	using namespace std;
	vector<ld> X(1001);
	vector<ld> Y(1001);
	ld n, l, ans, a, b;
	void arr_make(ld n){
	ld r1 = 0, r2 = 0;
	for (ld i = 0; i < n; i++){
	r1 += X[i]*Y[i+1];
	r2 += Y[i]*X[i+1];
	}
	ans = abs(r1-r2)/2;
	}
	int main() {
	fastio;
	for(;;){
	cin >> n;
	if (n == 0) break;
	else{
	for (ld i = 0; i < n; i++){
	cin >> a >> b;
	X[i] = a;
	Y[i] = b;
	}
	if (n <= 2){
	cout << 0 << '\n';
	continue;
	}
	X[n] = X[0];
	Y[n] = Y[0];
	}
	arr_make(n);
	cout << round(ans) << '\n';
	}
	}

view raw 3749.cpp hosted with ❤ by GitHub

---

 
문제 링크: https://www.acmicpc.net/problem/8421

8421번: Suma

---

 
8421번 Suma (2023-11-14 기준 Gold II)

 
d(n)은 쉽게 말해서 n의 약수의 개수이고, Sn은 d(1)부터 d(n)까지의 합이다. 당연스럽게도 제한이 ${10}^{12}$라서 Naive하게 돌리면 시간 초과를 받는다. 효율적으로 계산하기 위해서는 생각해보아야 할 점이 있다.
 
먼저, 1을 약수로 가지는 1~n까지의 수는 총 n개가 될 것이다. 왜냐하면 1은 모든 수의 약수이기 때문이다.
2를 약수로 가지는 1~n까지의 수는 총 n/2개가 될 것이다.
3을 약수로 가지는 1~n까지의 수는 총 n/3개가 될 것이다.
... 이렇게 하다보면 k를 약수로 가지는 1~n까지의 수는 총 n/k고 그 n/k가 이전의 i(1 <= i < k)가 되는 경우가 찾아오게 될 것이다.
 
이게 무슨 의미냐면, 예를 들어 10을 생각해보자.
1을 약수로 가지는 수의 개수는 총 10개(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).
2를 약수로 가지는 수의 개수는 총 5개(2, 4, 6, 8, 10).
3을 약수로 가지는 수의 개수는 총 3개(3, 6, 9).
4를 약수로 가지는 수의 개수는 총 2개(4, 8). -> 여기를 주목하자.
이전에 2와 지금 2가 겹치게 된다. 그리고 2일 때, 5였는데 그렇다는 건, 4~5를 약수로 가지는 수의 개수는 각각 2개라고 확정지을 수 있다. 즉, (5+1-4) * 2를 더해준다.
정말일까? 실제로 5를 약수로 가지는 수의 개수는 (5, 10)으로 2개가 맞고, 6은 1개(6)이므로, 정말로 맞다.
즉, 이렇게 ${10}^{12}$을 모두 탐색할 필요없이 이전에 있었던 값이 있는지 없는지 여부를 판단하여 빠르게 찾을 수 있다.
그러면, 6~10까지는 1개로 확정 지을 수 있기 때문에 4 이후로는 급격하게 탐색하는 개수가 줄어든다. 당연스럽게 이때는 (10-5+1) * 1을 더해주면 해결 완료.
따라서 정확한 시간 복잡도는 모르겠지만 $O(N)$보다 더 빠르게(아마 $O(\sqrt{N})$?) 구할 수 있다.
 

	n = int(input())
	ans, i, idx = 0, 1, -1
	d, lst = set(), []
	while i <= n:
	if n//i in d:
	lst.append((n//i, i-1))
	idx += 1
	break
	else:
	ans += n//i
	d.add(i)
	if n//i != i:
	lst.append((i, n//i))
	idx += 1
	i += 1
	for i in range(idx, 0, -1):
	ans += (lst[i-1][1]-lst[i][1])*lst[i-1][0]
	print(ans)

view raw 8421.py hosted with ❤ by GitHub

---

 
문제 링크: https://www.acmicpc.net/problem/1711

1711번: 직각삼각형

---

 
1711번 직각삼각형 (2023-11-15 기준 Gold V)

 
직각삼각형을 판별할 때, 중학교 때 배웠던 피타고라스 정리를 이용했다. 1500개의 점에서 3개를 뽑는 것은 $(\genfrac{}{}{0ex}{}{1500}{3})$이다. 즉, 561,375,500개이므로 5초 안에 돌아갈 수 있다 생각했다. 물론 $O(N^3)$의 풀이가 성공한 것은 맞으나, 약간의 최적화가 필요했었다. 실제로 몇 번 시간 초과가 났다. 임의의 변의 길이의 제곱(즉, 점과 점 사이의 거리에서 제곱근을 하지 않은 수) a, b, c이 있을 때, 가장 작은 수를 a(= min(a, b, c)), 중간 수를 b(= a+b+c-a-c), 가장 큰 수를 c(= max(a, b, c))로 한 다음에 a+b가 c와 같은 경우에서 2*max(a, b, c)가 a+b+c와 같은 경우로 변경했더니 정답을 맞췄다. 아마 min, max 연산도 은근 시간이 걸렸던 거 같다.
 

	import sys
	input = sys.stdin.readline
	def dist(d1, d2):
	x1, y1 = d1
	x2, y2 = d2
	return (x1-x2)**2 + (y1-y2)**2
	n = int(input())
	d = []
	for _ in range(n):
	d.append(tuple(map(int, input().split())))
	ans = 0
	for i in range(n):
	for j in range(i+1, n):
	for k in range(j+1, n):
	a, b, c = dist(d[i], d[j]), dist(d[i], d[k]), dist(d[j], d[k])
	if 2*max(a, b, c) == a+b+c: ans += 1
	print(ans)

view raw 1711.py hosted with ❤ by GitHub

---

문제 링크: https://www.acmicpc.net/problem/5567

5567번: 결혼식

---

 

5567번 결혼식 (2023-11-15 기준 Silver II)

 
단순히 dfs나 bfs로도 가능하고, 여러가지 가능하지만 나는 플로이드-와샬로 자신의 친구와 친구의 친구(= 자신과 거리가 2 이하인 경우)인 경우 1씩 더하는 방법으로 풀었다.
 
 

	import sys
	input = sys.stdin.readline
	INF = int(1e5)
	n, m = int(input()), int(input())
	graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
	for i in range(m):
	a, b = map(int, input().split())
	graph[a][b] = 1
	graph[b][a] = 1
	for k in range(1, n+1):
	for a in range(1, n+1):
	for b in range(1, n+1):
	graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
	ans = 0
	for i in range(2, n+1):
	if graph[1][i] <= 2:
	ans += 1
	print(ans)

view raw 5567.py hosted with ❤ by GitHub

---

문제 링크: https://www.acmicpc.net/problem/26535

26535번: Chicken Pen

---

26535번 Chicken Pen (2023-11-17 기준 Bronze III)

 
단순한 구현 문제. 별 찍기 보다는 조금 어려운 듯.
 
 

	n = int(input())
	x, y = 0, 1
	while True:
	if x**2 < n <= y**2:
	break
	x += 1; y += 1
	print("x"*(2+y))
	for _ in range(y):print("x"+"."*y+"x")
	print("x"*(2+y))

view raw 26535.py hosted with ❤ by GitHub

---

문제 링크: https://www.acmicpc.net/problem/20977

20977번: JOI ソート (JOI Sort)

---

 
20977번 JOI ソート (JOI Sort) (2023-11-18 기준 Bronze II)
 
커스텀 정렬도 가능하나 J, O, I의 개수를 세고나서 순서대로 문자를 출력해도 된다.
 
 

	n, s = int(input()), input()
	joi = [0, 0, 0]
	for i in range(n):
	if s[i] == 'J': joi[0] += 1
	elif s[i] == 'O': joi[1] += 1
	else: joi[2] += 1
	print("J"*joi[0]+"O"*joi[1]+"I"*joi[2])

view raw 20977.py hosted with ❤ by GitHub

---

문제 링크: https://www.acmicpc.net/problem/30676

30676번: 이 별은 무슨 색일까

---

30676번 이 별은 무슨 색일까 (2023-11-18 기준 Bronze V)
 
조건문을 이용하여 조건에 맞춰 출력하면 된다.
 
 

	import sys
	input = sys.stdin.readline
	n = int(input())
	if 620<=n<=780: print("Red")
	elif 590<=n<620: print("Orange")
	elif 570<=n<590: print("Yellow")
	elif 495<=n<570: print("Green")
	elif 450<=n<495: print("Blue")
	elif 425<=n<450: print("Indigo")
	else: print("Violet")

view raw 30676.py hosted with ❤ by GitHub