dev/algorithm
BOJ / 17626๋ฒ / Four Squares [Go][Python3]
crscnt
2021. 1. 21. 21:00
๐ฉ๐ป๐ป ๋ฌธ์
17626๋ฒ: Four Squares
๋ผ๊ทธ๋์ฃผ๋ 1770๋ ์ ๋ชจ๋ ์์ฐ์๋ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์์ ํฉ์ผ๋ก ํํํ ์ ์๋ค๊ณ ์ฆ๋ช ํ์๋ค. ์ด๋ค ์์ฐ์๋ ๋ณต์์ ๋ฐฉ๋ฒ์ผ๋ก ํํ๋๋ค. ์๋ฅผ ๋ค๋ฉด, 26์ 52๊ณผ 12์ ํฉ์ด๋ค; ๋ํ 42 + 32 + 1
www.acmicpc.net
โ๐ป ํ์ด
๐จ Go
// https://www.acmicpc.net/problem/17626
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var n int
fmt.Fscanln(reader, &n)
fmt.Fprintln(writer, getSquareCount(n))
}
func getSquareCount(n int) int {
dp := make([]int, n+1)
dp[1] = 1
for i := 2; i < n+1; i++ {
minCount := n
for j := 1; j*j <= i; j++ { // i๋ณด๋ค ์์ ์ ๊ณฑ์๋ค์ dp๊ฐ ์ค ์ต์๊ฐ์ ๊ตฌํ๋ค
if minCount > dp[i-j*j] {
minCount = dp[i-j*j]
}
}
dp[i] = minCount + 1 // ์ต์๊ฐ๊ณผ ํด๋น ์ ๊ณฑ์๋ฅผ ๋ํ๋ ๊ฒฝ์ฐ๋ก 1์ ๋ํ ๊ฐ์ dp[i]์ ์ ์ฅํ๋ค
}
return dp[n]
}
๐จ Python3
# https://www.acmicpc.net/problem/17626
import sys
def get_square_count(n):
min_count = 4
for i in range(int(n**0.5), 0, -1):
if i*i == n:
min_count = min(min_count, 1)
break
else:
new_n = n - i*i
for j in range(int(new_n**0.5), 0, -1):
if new_n == j*j:
min_count = min(min_count, 2)
break
else:
new_n2 = n - i*i - j*j
for k in range(int(new_n2**0.5), 0, -1):
if new_n2 == k*k:
min_count = min(min_count, 3)
return min_count
if __name__ == "__main__":
n = int(sys.stdin.readline())
print(get_square_count(n))
# ์๊ฐ ์ด๊ณผ ๋ฐ์
# def get_square_count(n):
# dp = [0 for i in range(n+1)]
# dp[1] = 1
# for i in range(2, n+1):
# min_count = n
# j = 1
# while j*j <= i:
# if min_count > dp[i-j*j]:
# min_count = dp[i-j*j]
# j += 1
# dp[i] = min_count + 1
# return dp[n]
728x90