๋ฌธ์ (์ถ์ฒ: 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'
์๊ฐ๐ค
์ ์ด ๋ฌธ์ ๊ฐ ์ด ๋์ด๋์ธ์ง ๋ชจ๋ฅด๊ฒ ์ง๋ง ์ฑ๊ณต -!
๋๋ฌด ๋จ์ํ๊ฒ ์๊ฐํ๊ณ ํ์ด์ ์ค๋ช ํ๊ธฐ ์ด๋ ต๋ค๐ถ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 10026_์ ๋ก์์ฝ (0) | 2022.03.20 |
---|---|
[Baekjoon] 4889_์์ ์ ์ธ ๋ฌธ์์ด (0) | 2022.03.18 |
[Baekjoon] 2553_๋ง์ง๋ง ํฉํ ๋ฆฌ์ผ ์ (0) | 2022.03.16 |
[Baekjoon] 9465_์คํฐ์ปค (0) | 2022.03.15 |
[Baekjoon] 2644_์ด์๊ณ์ฐ (0) | 2022.03.14 |