๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด/Binary Search3

[๋ฐฑ์ค€]2110๋ฒˆ: ๊ณต์œ ๊ธฐ ์„ค์น˜ https://www.acmicpc.net/problem/2110 2110๋ฒˆ: ๊ณต์œ ๊ธฐ ์„ค์น˜ ์ฒซ์งธ ์ค„์— ์ง‘์˜ ๊ฐœ์ˆ˜ N (2 ≤ N ≤ 200,000)๊ณผ ๊ณต์œ ๊ธฐ์˜ ๊ฐœ์ˆ˜ C (2 ≤ C ≤ N)์ด ํ•˜๋‚˜ ์ด์ƒ์˜ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ง‘์˜ ์ขŒํ‘œ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” xi (0 ≤ xi ≤ 1,000,000,000)๊ฐ€ www.acmicpc.net ์ฒ˜์Œ ํ’€์ด 1. ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์กฐํ•ฉ nCc๋ฅผ ๊ตฌํ•œ๋‹ค 2. ๊ฐ€์žฅ ๋–จ์–ด์ง„ ๋‘ ๊ณต์œ ๊ธฐ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ๋‹ค from itertools import combinations def minDist(arr): result=1e9 for i in range(len(arr)-1): result = min(result,arr[i+1]-arr[i]) return re.. 2023. 3. 10.
[๋ฐฑ์ค€]2512๋ฒˆ: ์˜ˆ์‚ฐ https://www.acmicpc.net/problem/2512 2512๋ฒˆ: ์˜ˆ์‚ฐ ์ฒซ์งธ ์ค„์—๋Š” ์ง€๋ฐฉ์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 3 ์ด์ƒ 10,000 ์ดํ•˜์ด๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” ๊ฐ ์ง€๋ฐฉ์˜ ์˜ˆ์‚ฐ์š”์ฒญ์„ ํ‘œํ˜„ํ•˜๋Š” N๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ด ๊ฐ’๋“ค์€ ๋ชจ๋‘ 1 ์ด์ƒ www.acmicpc.net (์ง€๋ฐฉ๋ณ„ ์š”์ฒญ์˜ˆ์‚ฐ ์ค‘ ์ตœ๋Œ“๊ฐ’)*N ์˜ ๊ฐ’์ด ์ด ์˜ˆ์‚ฐ M๋ณด๋‹ค ๊ฐ™๊ฑฐ๋‚˜ ํฐ ๊ฒฝ์šฐ์—๋Š” ์˜ˆ์‚ฐ์„ ๊ฐ ์ง€๋ฐฉ์ด ์š”์ฒญํ•œ ๋Œ€๋กœ ๋ฐฐ์ •ํ•ด์ฃผ๋ฉด ๋˜์ง€๋งŒ, ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ๋Š” ์ƒํ•œ์•ก์„ ๋ฐฐ์ •ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค. ๊ฐ„๋‹จํ•˜๊ฒŒ๋Š” ์„ ํ˜•ํƒ์ƒ‰์„ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์—ˆ๋Š”๋ฐ, ์ฃผ์–ด์ง„ m์˜ ๋ฒ”์œ„๊ฐ€ 1๋ถ€ํ„ฐ 1,000,000,000 ์‚ฌ์ด๋ผ๋Š” ์ ์ด ๊ฑธ๋ ธ๋‹ค. ๋ฌธ์ œ์—์„œ์˜ ์ œํ•œ์‹œ๊ฐ„์€ 1์ดˆ์ด๊ณ , ํŒŒ์ด์ฌ์€ 1์ดˆ๋™์•ˆ ์•ฝ 2000๋งŒ ๋ฒˆ์˜ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ์„ ํ˜•.. 2023. 2. 28.
[์ด์ฝ”ํ…Œ]๋–ก๋ณถ์ด ๋–ก ๋งŒ๋“ค๊ธฐ / [๋ฐฑ์ค€]2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ https://www.acmicpc.net/problem/2805 2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ ์ฒซ์งธ ์ค„์— ๋‚˜๋ฌด์˜ ์ˆ˜ N๊ณผ ์ƒ๊ทผ์ด๊ฐ€ ์ง‘์œผ๋กœ ๊ฐ€์ ธ๊ฐ€๋ ค๊ณ  ํ•˜๋Š” ๋‚˜๋ฌด์˜ ๊ธธ์ด M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) ๋‘˜์งธ ์ค„์—๋Š” ๋‚˜๋ฌด์˜ ๋†’์ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‚˜๋ฌด์˜ ๋†’์ด์˜ ํ•ฉ์€ ํ•ญ์ƒ M๋ณด www.acmicpc.net ๋‘˜์ด ๊ฐ™์€ ๋ฌธ์ œ์ž„ ์ฒ˜์Œ์—๋Š” ๋‹จ์ˆœํ•˜๊ฒŒ ๋ฐฐ์—ด์„ ์ •๋ ฌ์„ ํ•˜๊ณ , ๋†’์ด๋ฅผ ๋ฐฐ์—ด์š”์†Œ์˜ ์ตœ๋Œ“๊ฐ’์œผ๋กœ๋ถ€ํ„ฐ 1์”ฉ ์ค„์—ฌ๋‚˜๊ฐ€๋ฉฐ ๋งค๋ฒˆ ์ž˜๋ฆฐ ๋‚˜๋ฌด์˜ ๊ธธ์ด๋ฅผ ๊ณ„์‚ฐ, ๋น„๊ตํ•ด๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹์„ ์ƒ๊ฐํ–ˆ๋‹ค ๊ทผ๋ฐ ์ด๊ฑด ๋„ˆ๋ฌด ๋ฌด์‹ํ•œ ๋ฐฉ๋ฒ•์ด๊ธฐ๋„ ํ•˜๊ณ  ๋ฌด์—‡๋ณด๋‹ค ์‹œ๊ฐ„์ด ์—„์ฒญ ์˜ค๋ž˜ ๊ฑธ๋ฆด ๊ฒƒ ๊ฐ™์•˜์Œ ๊ทธ๋ž˜์„œ ์ด์ง„ํƒ์ƒ‰์œผ๋กœ ํ’€์—ˆ๋‹ค. ์ด์ง„ํƒ์ƒ‰์œผ๋กœ ํ’€๋ฉด ํƒ์ƒ‰๋ฒ”์œ„๋ฅผ ์ ˆ๋ฐ˜์”ฉ ์ค„์—ฌ๊ฐ€๋ฉฐ ํ’€ ์ˆ˜ ์žˆ์œผ๋‹ˆ ์—ฐ์‚ฐ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด ๋ˆˆ์— .. 2023. 2. 24.
728x90