ํฐ์คํ ๋ฆฌ ๋ทฐ
๐ฉ๐ปโ๐ป ๋ฌธ์
โ๐ป ํ์ด
๐จ Go
// https://www.acmicpc.net/problem/2110
// ์ด๋ถ ํ์์ ์์ฉํ์ฌ ์ต์๊ฐ์ด๋ ์ต๋๊ฐ์ ์ฐพ๋ ๋ฌธ์ 3
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var n, c int
fmt.Fscanln(reader, &n, &c)
var x = make([]int, n)
for i := 0; i < n; i++ {
fmt.Fscanln(reader, &x[i])
}
sort.Ints(x)
fmt.Fprintln(writer, getRouterDistacne(x, c))
}
func getRouterDistacne(x []int, c int) (dist int) {
var start = 1 // ์ต์ ๊ฐ๊ฒฉ
var end = x[len(x)-1] - x[0] // ์ต๋ ๊ฐ๊ฒฉ
for start <= end {
mid := (start + end) / 2
prev := x[0]
count := 1
for i := 1; i < len(x); i++ {
temp := x[i] - prev
if mid <= temp {
count++
prev = x[i]
}
}
if count >= c {
dist = mid
start = mid + 1 // ๊ฐ๊ฒฉ์ ๋ํ๋ค
} else {
end = mid - 1 // ๊ฐ๊ฒฉ์ ์ขํ๋ค
}
}
return
}
๐จ Python3
# https://www.acmicpc.net/problem/2110
# ์ด๋ถ ํ์์ ์์ฉํ์ฌ ์ต์๊ฐ์ด๋ ์ต๋๊ฐ์ ์ฐพ๋ ๋ฌธ์ 3
import sys
def get_router_distance(x, c):
start = 1
end = x[-1]-x[0]
dist = 0
while start <= end:
mid = (start + end) // 2
prev = x[0]
count = 1
for i in range(len(x)):
temp = x[i] - prev
if mid <= temp :
count += 1
prev = x[i]
if count >= c:
dist = mid
start = mid + 1
else:
end = mid - 1
return dist
if __name__ == "__main__":
n, c = map(int, sys.stdin.readline().split())
x = []
for i in range(n):
x.append(int(sys.stdin.readline()))
x.sort()
print(get_router_distance(x, c))
728x90
'dev > algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
BOJ / 1764๋ฒ / ๋ฃ๋ณด์ก [Go][Python3] (0) | 2020.11.27 |
---|---|
BOJ / 10815๋ฒ / ์ซ์ ์นด๋ [Go][Python3] (0) | 2020.11.26 |
BOJ / 20207๋ฒ / ๋ฌ๋ ฅ [Go] (0) | 2020.11.24 |
BOJ / 20206๋ฒ / ํธ์์ด๊ฐ ๊ธธ์ ๊ฑด๋๊ฐ ์ด์ [Go] (0) | 2020.11.23 |
BOJ / 20205๋ฒ / ๊ต์๋ ๊ทธ๋ฆผ์ด ๊นจ์ง๋๋ฐ์? [Go] (0) | 2020.11.22 |
๋๊ธ
๊ธ ๋ณด๊ดํจ
์ต๊ทผ์ ๋ฌ๋ฆฐ ๋๊ธ
TAG
- go
- baekjoon
- dp
- java
- BFS
- ํ๋ก์ด๋์์ฌ
- ์ด๋ถํ์
- MongoDB
- ๋งฅ๋ถ
- Algorithm
- ํด์๋งต
- ๋ฐฑ์ค
- ์๋ฐ
- ๋งฅ๋ถํ๋ก
- python3
- Golang
- ๋ฐ๋
- ballet
- ๋ถํ ์ ๋ณต
- ์๊ณ ๋ฆฌ์ฆ
- ํ
- dfs
- Macbook pro 2012 mid 13
- BOJ
- ๋ชฝ๊ณ ๋๋น
- ๋งฅ๋ถ ์ ๊ทธ๋ ์ด๋
- ์คํ
- ์๊ฐ๊ต์ฒด
- ๋ธ๋ฃจํธํฌ์ค
- AWS
- Total
- Today
- Yesterday