[λ°±μ€€] 1011 Fly me to the Alpha Centauri

eunbiΒ·2022λ…„ 8μ›” 9일
0
post-thumbnail

πŸ” 1011 Fly me to the Alpha Centauri

μš°ν˜„μ΄λŠ” μ–΄λ¦° μ‹œμ ˆ, 지ꡬ μ™Έμ˜ λ‹€λ₯Έ ν–‰μ„±μ—μ„œλ„ 인λ₯˜λ“€μ΄ μ‚΄μ•„κ°ˆ 수 μžˆλŠ” λ―Έλž˜κ°€ 였리라 λ―Ώμ—ˆλ‹€. 그리고 κ·Έκ°€ μ§€κ΅¬λΌλŠ” 세상에 λ°œμ„ λ‚΄λ € 놓은 μ§€ 23년이 μ§€λ‚œ μ§€κΈˆ, 세계 μ΅œμ—°μ†Œ ASNA 우주 비행사가 λ˜μ–΄ μƒˆλ‘œμš΄ 세계에 λ°œμ„ λ‚΄λ € λ†“λŠ” μ˜κ΄‘μ˜ μˆœκ°„μ„ 기닀리고 μžˆλ‹€.

κ·Έκ°€ νƒ‘μŠΉν•˜κ²Œ 될 μš°μ£Όμ„ μ€ Alpha CentauriλΌλŠ” μƒˆλ‘œμš΄ 인λ₯˜μ˜ 보금자리λ₯Ό κ°œμ²™ν•˜κΈ° μœ„ν•œ λŒ€κ·œλͺ¨ μƒν™œ μœ μ§€ μ‹œμŠ€ν…œμ„ νƒ‘μž¬ν•˜κ³  있기 λ•Œλ¬Έμ—, κ·Έ 크기와 μ§ˆλŸ‰μ΄ μ—„μ²­λ‚œ 이유둜 μ΅œμ‹ κΈ°μˆ λ ₯을 총 λ™μ›ν•˜μ—¬ κ°œλ°œν•œ 곡간이동 μž₯치λ₯Ό νƒ‘μž¬ν•˜μ˜€λ‹€. ν•˜μ§€λ§Œ 이 곡간이동 μž₯μΉ˜λŠ” 이동 거리λ₯Ό κΈ‰κ²©ν•˜κ²Œ 늘릴 경우 기계에 μ‹¬κ°ν•œ 결함이 λ°œμƒν•˜λŠ” 단점이 μžˆμ–΄μ„œ, 이전 μž‘λ™μ‹œκΈ°μ— k광년을 μ΄λ™ν•˜μ˜€μ„ λ•ŒλŠ” k-1 , k ν˜Ήμ€ k+1 κ΄‘λ…„λ§Œμ„ λ‹€μ‹œ 이동할 수 μžˆλ‹€. 예λ₯Ό λ“€μ–΄, 이 μž₯치λ₯Ό 처음 μž‘λ™μ‹œν‚¬ 경우 -1 , 0 , 1 광년을 이둠상 이동할 수 μžˆμœΌλ‚˜ 사싀상 음수 ν˜Ήμ€ 0 거리만큼의 이동은 μ˜λ―Έκ°€ μ—†μœΌλ―€λ‘œ 1 광년을 이동할 수 있으며, κ·Έ λ‹€μŒμ—λŠ” 0 , 1 , 2 광년을 이동할 수 μžˆλŠ” 것이닀. ( μ—¬κΈ°μ„œ λ‹€μ‹œ 2광년을 μ΄λ™ν•œλ‹€λ©΄ λ‹€μŒ μ‹œκΈ°μ—” 1, 2, 3 광년을 이동할 수 μžˆλ‹€. )

κΉ€μš°ν˜„μ€ 곡간이동 μž₯치 μž‘λ™μ‹œμ˜ μ—λ„ˆμ§€ μ†Œλͺ¨κ°€ ν¬λ‹€λŠ” 점을 잘 μ•Œκ³  있기 λ•Œλ¬Έμ— xμ§€μ μ—μ„œ y지점을 ν–₯ν•΄ μ΅œμ†Œν•œμ˜ μž‘λ™ 횟수둜 μ΄λ™ν•˜λ € ν•œλ‹€. ν•˜μ§€λ§Œ y지점에 λ„μ°©ν•΄μ„œλ„ 곡간 이동μž₯치의 μ•ˆμ „μ„±μ„ μœ„ν•˜μ—¬ y지점에 λ„μ°©ν•˜κΈ° λ°”λ‘œ μ§μ „μ˜ μ΄λ™κ±°λ¦¬λŠ” λ°˜λ“œμ‹œ 1κ΄‘λ…„μœΌλ‘œ ν•˜λ € ν•œλ‹€.

κΉ€μš°ν˜„μ„ μœ„ν•΄ x지점뢀터 μ •ν™•νžˆ yμ§€μ μœΌλ‘œ μ΄λ™ν•˜λŠ”λ° ν•„μš”ν•œ 곡간 이동 μž₯치 μž‘λ™ 횟수의 μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜λΌ.


πŸ€” 풀이

  • 뭐야 λ§ˆμ§€λ§‰ 경우λ₯Ό μ œμ™Έν•˜κ³  λ‹¨μˆœν•œ λ“±μ°¨μˆ˜μ—΄ μ•„λ‹Œκ°€..? μ‹Άμ—ˆλŠ”λ° 문제λ₯Ό 잘λͺ» μ΄ν•΄ν•˜κ³  μžˆμ—ˆλ‹€.
  • 이전에 kκ΄‘λ…„ μ΄λ™ν–ˆλ‹€λ©΄, μ΄λ²ˆμ—λŠ” k-1 or k or k+1 κ΄‘λ…„λ§ŒνΌ 이동 ν•  수 μžˆλ‹€.
    • λ§ˆμ§€λ§‰(N)은 κΌ­ 1광년을 이동해야 ν•˜λ―€λ‘œ, μœ„ 쑰건을 λ”°λ₯΄λ©΄ N-1λ²ˆμ§Έμ—λŠ” 2κ΄‘λ…„ λ˜λŠ” 1광년이어야 ν•œλ‹€.
  • 처음 μœ„μΉ˜, 도착 지점이 μ–΄λ””λ“  κ·Έ 사이 거리 dκ°€ 문제의 정닡을 μ’Œμš°ν•œλ‹€.
  • dλ₯Ό κΈ°μ€€μœΌλ‘œ μ •λ‹΅ ν…Œμ΄λΈ”μ„ λ§Œλ“€λ©΄ λ‹€μŒκ³Ό κ°™μœΌλ©° κ·œμΉ™μ΄ 보인닀.
d이동 거리이용 횟수
111
21 12
31 1 13
41 2 13
51 2 1 14
61 2 2 14
71 2 2 1 15
81 2 2 2 15
101 2 3 2 1 16
111 2 3 2 2 16
121 2 3 3 2 16
131 2 3 3 2 1 17
141 2 3 3 2 2 17
151 2 3 3 3 2 17
161 2 3 4 3 2 17
171 2 3 4 3 2 1 18
181 2 3 4 3 2 2 18
191 2 3 4 3 3 2 18
201 2 3 4 4 3 2 18
  • ν•΄λ‹Ή ν…Œμ΄λΈ”μ„ κ°„λž΅ν™”ν•˜λ©΄ μ•„λž˜μ²˜λŸΌ λ‚˜νƒ€λ‚Ό 수 μžˆλŠ”λ°, 이용 νšŸμˆ˜μ— 따라 그에 ν•΄λ‹Ήλ˜λŠ” dλ“€μ˜ κ°œμˆ˜λ„ λŠ˜μ–΄λ‚˜λŠ” 것을 λ³Ό 수 μžˆλ‹€. 두 개 ν–‰μ˜ κ°œμˆ˜κ°€ κ°™κ³ , κ·Έ λ‹€μŒ κ°œμˆ˜κ°€ λŠ˜μ–΄λ‚˜λ―€λ‘œ λ‘κ°œ 행을 ν•œ ν•­μœΌλ‘œ 보고 이λ₯Ό a=2,d=2a=2, d=2인 λ“±μ°¨μˆ˜μ—΄λ‘œ λ‚˜νƒ€λ‚΄λ©΄ λ“±μ°¨μˆ˜μ—΄μ˜ 합을 μ΄μš©ν•΄ μž…λ ₯받은 d의 이용 횟수λ₯Ό ꡬ할 수 μžˆλ‹€. λ”°λΌμ„œ (Nβˆ’1)2+(Nβˆ’1)≀d≀(N)2+N(N-1)^2+(N-1)\leq d\leq(N)^2+Nλ₯Ό λ§Œμ‘±ν•˜λŠ” N을 κ΅¬ν•œλ‹€. (λ„ˆλ¬΄ λ³΅μž‘ν•˜κ²Œ κ΅¬ν•œλ“― ν•˜λ‹€...)
d이용 횟수
11
22
3, 43
5, 64
7, 8, 95
10, 11, 126
13, 14, 15, 167
17, 18, 19, 208

  • κ΅¬ν•œ N은 ν•œ ν•­μ˜ 첫번째 행이면 N-1이고, λ‘λ²ˆμ§Έ 행이면 N의 닡을 κ°€μ§€λ―€λ‘œ μ–΄λ”” μ†ν•œμ§€ νŒλ‹¨μ„ 톡해 닡을 좜λ ₯ν•œλ‹€.

πŸ“ μ½”λ“œ

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);

    int x, y;
    for (int i = 0; i < T; i++) {
        scanf("%d %d", &x, &y);
        long long int sum = 0;
        int d = y-x;
        int dx = 1;
        while (d > sum + 2*dx) {
            sum = sum + 2*dx;
            dx++;
        }
        if (sum + dx >= d) printf("%d\n", 2*dx - 1);
        else printf("%d\n", 2*dx);
    }

    return 0;
}

0개의 λŒ“κΈ€