[백준 / Go] 9417번: 최대 GCD

문제

9417번: 최대 GCD

정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -2³¹보다 크거나 같고, 2³¹ -1보다 작거나 같다. 

출력

각 테스트 케이스마다, 입력으로 주어진 수의 모든 두 수의 쌍의 최대공약수 중 가장 큰 값을 출력한다.

---

문제 이해하기

 완전 탐색으로 입력으로 주어진 수의 모든 두 수의 쌍 중 최대공약수가 가장 큰 값을 구하면 됩니다.

---

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	writer  = bufio.NewWriter(os.Stdout)
	T       int
)

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanLines)

	Setup()
	Solve()
}

func Setup() {
	T = scanInt()
}

func Solve() {
	for i := 0; i < T; i++ {
		b := scanBytes()
		var arr []int

		n := 0
		for i := 0; i < len(b); i++ {
			if b[i] == ' ' {
				arr = append(arr, n)
				n = 0
				continue
			}

			n = n*10 + int(b[i]-'0')
		}

		arr = append(arr, n)

		max := 0

		for a := 0; a < len(arr)-1; a++ {
			for b := a + 1; b < len(arr); b++ {
				g := gcd(arr[a], arr[b])
				if g > max {
					max = g
				}
			}
		}

		fmt.Fprintln(writer, max)
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func scanBytes() []byte {
	scanner.Scan()
	return scanner.Bytes()
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

시간: 4 ms

메모리:860 KB

분류: 수학, 브루트포스 알고리즘, 정수론, 유클리드 호제법

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!