구구단 걷기

첫번째 코드

 

이전에 곱셈식을 만드는 알고리즘을 이용하면 된다.

이때 중요한 것은 1 * 5와 5 * 1은 모두 같고 메모리만 사용하기 떄문에

1부터 int(5 ** 0.5) + 1까지만 확인하면 되는 것이다!

 

최소한으로 움직이는 방법은 가장 작은 수의 곱들로 해당 수를 만들면 된다!

즉 25의 경우 1 * 25보다 5 * 5가 가장 작은 수의 곱들이고, 가장 적게 움직이는 방법이다. 

 

또한 (1, 1)부터 시작하므로 내려가는 크기는 각각의 가로 세로 몫에 1씩 빼야 한다는 것이다.

 

question_num = int(input())

for i in range(1, question_num + 1):
    n = int(input())

    multi = 1

    for j in range(1, int(n**0.5) + 1):
        if n % j == 0:
            multi = max(multi, j)
        
    answer1 = multi - 1
    answer2 = (n // multi) - 1

    print(f"#{i} {answer1 + answer2}")

 

D2는 괜찮았던 것 같고 D4는 어려웠던 것 같아서 D3문제를 풀어봤다.

기초 알고리즘이 적용되는 문제들이 나오려나?

통과!

---

링크

https://github.com/ornni/programmers/tree/main/SWEA/D3/16800.%E2%80%85%EA%B5%AC%EA%B5%AC%EB%8B%A8%E2%80%85%EA%B1%B7%EA%B8%B0

programmers/SWEA/D3/16800. 구구단 걷기 at main · ornni/programmers