๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 1850_์ตœ๋Œ€๊ณต์•ฝ์ˆ˜

๋ฟŒ์•ผ._. 2022. 3. 17. 15:45

Silver II

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/1850)

<์ตœ๋Œ€๊ณต์•ฝ์ˆ˜>

๋ฌธ์ œ 

 

๋ชจ๋“  ์ž๋ฆฌ๊ฐ€ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๋Š” ๋‘ ์ž์—ฐ์ˆ˜ A์™€ B๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, A์™€ B์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.
์˜ˆ๋ฅผ ๋“ค์–ด, A๊ฐ€ 111์ด๊ณ , B๊ฐ€ 1111์ธ ๊ฒฝ์šฐ์— A์™€ B์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋Š” 1์ด๊ณ , A๊ฐ€ 111์ด๊ณ , B๊ฐ€ 111111์ธ ๊ฒฝ์šฐ์—๋Š” ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๊ฐ€ 111์ด๋‹ค.

 

 

์ž…๋ ฅ

 

์ฒซ์งธ ์ค„์— ๋‘ ์ž์—ฐ์ˆ˜ A์™€ B๋ฅผ ์ด๋ฃจ๋Š” 1์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ๋˜๋Š” ์ˆ˜๋Š” 2์˜ 63์Šน๋ณด๋‹ค ์ž‘์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

 

์ถœ๋ ฅ 

 

์ฒซ์งธ ์ค„์— A์™€ B์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต์€ ์ฒœ๋งŒ ์ž๋ฆฌ๋ฅผ ๋„˜์ง€ ์•Š๋Š”๋‹ค.

 

 

๋ฌธ์ œ ํ’€์ด

- my solution

import sys

def gcd(a,b): #์ตœ๋Œ€๊ณต์•ฝ์ˆ˜
    if b==0:
        return a
    return gcd(b,a%b)

if __name__=='__main__':
    a,b=map(int, sys.stdin.readline().split())

    result=gcd(a,b)
    print('1'*result)

 

๋ฌธ์ œ๋ฅผ ๋ณด์ž๋งˆ์ž gcd๋ฅผ ์‚ฌ์šฉํ•ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์–ด ํ›„๋”ฑ ํ’€๊ณ  ๋ณด๋‹ˆ ๋งž์•˜์Šต๋‹ˆ๋‹ค๊ฐ€ ๋– ์žˆ์—ˆ๋‹ค.

1๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ  1์„ ์ด๋ฃจ๋Š” ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒƒ์ด๋ฏ€๋กœ 1์˜ ๊ฐœ์ˆ˜๋กœ๋งŒ gcd๋ฅผ ํ•ด๋„ ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋ผ ์ƒ๊ฐํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

 

  • ์ž์—ฐ์ˆ˜ A, B๋ฅผ ์ด๋ฃจ๋Š” 1์˜ ๊ฐœ์ˆ˜ ์ž…๋ ฅ
  • 1์„ ์ด๋ฃจ๋Š” ๊ฐœ์ˆ˜๋ผ๋ฆฌ gcd (์ตœ๋Œ€๊ณต์•ฝ์ˆ˜) ๊ตฌํ•˜๊ธฐ
  • answer: gcd ๊ฒฐ๊ณผ * '1'

์ƒ๊ฐ๐Ÿค”

 

์™œ ์ด ๋ฌธ์ œ๊ฐ€ ์ด ๋‚œ์ด๋„์ธ์ง€ ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ์„ฑ๊ณต -!

๋„ˆ๋ฌด ๋‹จ์ˆœํ•˜๊ฒŒ ์ƒ๊ฐํ•˜๊ณ  ํ’€์–ด์„œ ์„ค๋ช…ํ•˜๊ธฐ ์–ด๋ ต๋‹ค๐Ÿ˜ถ