728x90
문제
https://www.acmicpc.net/problem/2485
문제 이해
가로수들이 직선의 도로 한편에 심어져 있고 추가로 가로수를 심어 모든 가로수의 간격이 일정하게 되도록 하려고 한다.
이때 최소한으로 가로수를 심으려고 하는데 그 때의 가로수의 갯수를 출력해야 한다.
문제를 해결하기 위해서는 가로수 사이의 간격들을 구하고 모든 가로수 사이 간격들의 최대 공약수를 구해야 한다.
문제 해결
- 가로수들 사이의 간격을 side 벡터에 저장함.
- side 벡터의 원소들의 최대공약수를 구함.
- side 벡터의 간격들을 구한 최대공약수인 maxT로 나누고 -1 한 값을 count에 저장하여 결과를 출력했습니다.
728x90
'Coding' 카테고리의 다른 글
[C++]백준 1182번: 부분수열의 합 (0) | 2023.07.09 |
---|---|
[C++]백준 2644번: 촌수계산 (0) | 2023.07.08 |
[C++]백준 10816번: 숫자 카드 2 (0) | 2023.07.07 |
[C++]백준 14891번: 톱니바퀴 (0) | 2023.07.06 |
[C++]백준 2579번: 계단 오르기 (0) | 2023.07.05 |