1. 문제링크
https://www.acmicpc.net/problem/1011
2. 풀이 전 계획과 생각
< 정보 정리 >
1) 입력값: 테스트 케이스 T, 시작점 N, 도착점 M
2) 출력값: 이동 수 N
3) 제약조건:
- 0 <= 시작점 < 도착점 < 2^31
- 이전 이동거리가 k일 경우 다음 이동거리는 k-1, k, k+1이 가능
- 도착 직전 이동거리는 무조건 1k
4) 예외케이스: 없음
< 공통 로직 >
- 이동 거리 5 일때,
1) 최소 이동 횟수: 1k => 2k => 1k => 1k or 1k => 1k => 2k => 1k
2) 최대 이동 횟수: 1k => 1k => 1k => 1k => 1k
3) 최소 이동 횟수를 구하기 때문에 1) 을 찾는다
3. 풀이
def calc_alpha_centauri():
t = int(input("Enter the number of test cases:"))
result = [];
for i in range(t):
x = int(input(f"{i + 1} Enter starting point: "))
y = int(input(f"{i + 1} Enter ending point: "))
distance = y - x
count = 0
travel = 1
current_distance = 0
while current_distance < distance :
count += 1
current_distance += travel
if count % 2 == 0 :
travel += 1
result.append(count)
for i in result:
print(i)
calc_alpha_centauri()4. 풀이하면서 막혔던 점과 고민
처음에 문제를 풀때 꼭 이동거리를 맞게 숫자를 맞춰줘야한다는 것에 집중해서 정작 문제가 요구하는count값을 찾는 것을 간과했던 것 같다.
5. 풀이 후 알게된 개념과 소감
count를 찾기 위해 꼭 이동거리를 맞춰줘야할 필요가 없다는 것을 깨닫고 임의로 정의한 로직
if count % 2 == 0 :
travel += 1 으로 이동횟수를 추측할 수 있었다. 다만 문제가 "가능한 이동방법"을 나열하라 요구했다면 다른 식으로 풀어야할 것 같다.
