반응형
문제
나의 풀이
소스코드
t = int(input())
for _ in range(t):
x, y = map(int, input().split())
distance = y - x # y와 x사이의 거리
tmp = 0 # 이동 거리
cnt = 0 # 공간 장치 이동 횟수
moving = 0 # 반복 횟수
while tmp < distance:
cnt += 1
if cnt % 2 != 0:
moving += 1
tmp += moving
print(cnt)
해설
백준 단계별 풀어보기 하는 중 안풀려서 며칠 고민했던 문제다.
수학 유형은 직접 나열해보면서 규칙성을 파악해야한다.
특히, 문제에서 종료조건을 제대로 설정안해서 처음에 비효율적이고, 시간 초과가 나오는 코드를 만들었다.
1. 공간 장치 이동 횟수는 (공간 장치 이동 횟수 % 2) 만큼 반복되고,
2. 공간 장치 이동 횟수가 홀수가 될 때 마다 반복되는 횟수가 증가하는
규칙이 있음을 확인할 수 있다.
1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 ..이런식으로..
1) 변수 정의
이동한 거리를 세는 임시 변수 tmp, 공간 장치 이동 횟수인 cnt, 공간 장치 이동 횟수가 반복되는 수를 moving으로 정의했다.
distance = y - x # y와 x사이의 거리
tmp = 0 # 이동 거리
cnt = 0 # 공간 장치 이동 횟수
moving = 0 # 반복 횟수
2) 이동 하기
공간 장치 이동 횟수가 홀수일 때마다 반복 횟수를 증가 시키고,
공간 장치 이동 횟수를 (공간 장치 이동 횟수 % 2) 만큼 반복시킨다.
cnt += 1
if cnt % 2 != 0:
moving += 1
tmp += moving
3) 종료 조건
tmp < distance
이동한 거리가 distance보다 커지면 cnt(공간 장치 인동 횟수) 값을 갱신하는 것을 중단한다.
반응형
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준 1929] 소수 구하기 (+에라토스테네스의 체) python (0) | 2022.02.04 |
---|---|
[백준 11653] 소인수 분해 python (0) | 2022.02.04 |
[백준 2869] 달팽이는 올라가고 싶다 python (0) | 2022.02.02 |
[백준 1157] 단어 공부 python (0) | 2022.02.02 |
[백준 2577] 숫자의 개수 python (0) | 2022.02.02 |