[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 해주면 되는 문제. 사실 이 날에는 문제 풀기 귀찮아서 브론즈 풀었다..

 

---

 

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

3749번: Build Your Home

---

 

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

 

다각형의 넓이를 구하는 문제. 흔히 고등학교 때 배웠던 신발끈 공식을 이용했다.

원래는 Python으로 구현을 했는데 계속 IndexError가 떠서 정규 표현식으로 whitespace를 다 지웠는데도 안되어서 그냥 C++로 구현했다.

 

---

 

문제 링크: 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(logN)$?) 구할 수 있다.

 

---

 

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

1711번: 직각삼각형

---

 

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

 

직각삼각형을 판별할 때, 중학교 때 배웠던 피타고라스 정리를 이용했다. 1500개의 점에서 3개를 뽑는 것은 $\binom{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 연산도 은근 시간이 걸렸던 거 같다.

 

---

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

5567번: 결혼식

---

 

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

 

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

 

 

---

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

26535번: Chicken Pen

---

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

 

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

 

 

---

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

20977번: JOI ソート (JOI Sort)

---

 

20977번 JOI ソート (JOI Sort) (2023-11-18 기준 Bronze II)

 

커스텀 정렬도 가능하나 J, O, I의 개수를 세고나서 순서대로 문자를 출력해도 된다.

 

 

---

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

30676번: 이 별은 무슨 색일까

---

30676번 이 별은 무슨 색일까 (2023-11-18 기준 Bronze V)

 

조건문을 이용하여 조건에 맞춰 출력하면 된다.