본문 바로가기

2025/05/27

[Python] 백준 17087번: 숨바꼭질 6
[Python] 백준 17087번: 숨바꼭질 6 https://www.acmicpc.net/problem/17087 [풀이]최대 공약수를 구하면 간단히 해결되는 문제이다. 테스트케이스 1번을 예시로 들면, 수빈의 위치는 3동생들의 위치는 각각 1, 7, 11이다. 수빈의 위치와 비교해서 상대적인 거리를 측정하기 위해서는 각 거리의 차에 대한 절댓 값이 필요하다.이를 계산하면 2, 4, 8이 된다. 해당하는 거리들을 서로 비교하여 최대 공약수를 구할 수 있다면, 이번 문제의 답을 얻을 수 있다.이는, 유클리드 호제법을 통해 결과를 얻을 수 있을 것이다. (https://wikidocs.net/205459) --- 기본적으로, a와 b에 대한 최대 공약수를 구하기 위해서는 a와 b 중 작은 숫자로 먼저 나누어 보고,숫자의 크기를 1씩 줄여나가면서 나.. CS/Algorithm 2025. 5. 27.
[Python] 백준 1964번: 오각형, 오각형, 오각형…
[Python] 백준 1964번: 오각형, 오각형, 오각형… https://www.acmicpc.net/problem/1964 [풀이]처음에는 이렇게 나누어 풀었었다.좌측 하단의 꼭짓점을 기준으로, 중앙의 점 1개그 외 꼭짓점으로부터 뻗어나가는 부분 4개에 대해 (n-1)개그리고 나머지 3개 부분에 대한 (n-1)!개의 꼭짓점을 합해서1 + 4n + 3 * (n - 1)! 개라고 식을 도출했었다. 하지만, 이렇게 하면 factorial을 사용해야 했기 때문에, 더 좋은 방식을 찾고자 했다.등차수열을 이용하는 것이다. 우선, 전체에 대해 각각의 오각형을 중복을 생각하지 않고 개수를 구한다면5 + 10 + 15 + 20 + ... 5 * n 개의 꼭짓점이 나올 것이고이것을 공식화 한다면 5 * (n * (n - 1)) / 2 라는 공식이 나온다.1, 2, 3.. CS/Algorithm 2025. 5. 27.

티스토리툴바