๋ฐฑ์ค€ 18513๋ฒˆ : ์ƒ˜ํ„ฐ
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/18513 18513๋ฒˆ: ์ƒ˜ํ„ฐ ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N๊ณผ K๊ฐ€ ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N, K ≤ 100,000) ๋‘˜์งธ ์ค„์— N๊ฐœ์˜ ์ƒ˜ํ„ฐ์˜ ์œ„์น˜๊ฐ€ ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ •์ˆ˜ ํ˜•ํƒœ๋กœ ์ฃผ์–ด์ง„๋‹ค. (-100,000,000 ≤ ์ƒ˜ํ„ฐ์˜ ์œ„์น˜ ≤ www.acmicpc.net ๋ฌธ์ œ ์ผ์ง์„  ์ƒ์˜ ๊ณต๊ฐ„์— N๊ฐœ์˜ ์ƒ˜ํ„ฐ๊ฐ€ ์กด์žฌํ•˜๋ฉฐ, K์ฑ„์˜ ์ง‘์„ ์ง“๊ณ ์ž ํ•œ๋‹ค. ๋ชจ๋“  ์ƒ˜ํ„ฐ ๋ฐ ์ง‘์ด ์กด์žฌํ•˜๋Š” ์œ„์น˜๋Š” ํ•ญ์ƒ ์ •์ˆ˜ ํ˜•ํƒœ์ด๋‹ค. ์ด๋•Œ ์ผ์ง์„  ์ƒ์˜ ๊ณต๊ฐ„์—์„œ N๊ฐœ์˜ ์ƒ˜ํ„ฐ ๋ฐ K์ฑ„์˜ ์ง‘๋“ค์€ ๋ชจ๋‘ ์„œ๋กœ ๋‹ค๋ฅธ ์œ„์น˜์— ์กด์žฌํ•œ๋‹ค. K์ฑ„์˜ ์ง‘์„ ์ง€์„ ๋•Œ, ๊ฐ€๋Šฅํ•˜๋ฉด ์ƒ˜ํ„ฐ์˜ ์ฃผ๋ณ€์— ์ง‘๋“ค์„ ์ง€์–ด์„œ K์ฑ„์˜ ๋ชจ๋“  ์ง‘์— ๋Œ€ํ•œ ๋ถˆํ–‰๋„์˜ ํ•ฉ์ด ์ตœ์†Œ๊ฐ€ ๋˜๋„๋ก ์ง“๊ณ ์ž ํ•œ๋‹ค. ๋ถˆํ–‰๋„๋ž€, ๊ฐ€์žฅ ..
๋ฐฑ์ค€ 1937๋ฒˆ : ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/1937 1937๋ฒˆ: ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค n × n์˜ ํฌ๊ธฐ์˜ ๋Œ€๋‚˜๋ฌด ์ˆฒ์ด ์žˆ๋‹ค. ์š•์‹ฌ์Ÿ์ด ํŒ๋‹ค๋Š” ์–ด๋–ค ์ง€์—ญ์—์„œ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋จน๊ธฐ ์‹œ์ž‘ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๊ณณ์˜ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋‹ค ๋จน์–ด ์น˜์šฐ๋ฉด ์ƒ, ํ•˜, ์ขŒ, ์šฐ ์ค‘ ํ•œ ๊ณณ์œผ๋กœ ์ด๋™์„ ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋˜ ๊ทธ๊ณณ์— www.acmicpc.net ๋ฌธ์ œ n × n์˜ ํฌ๊ธฐ์˜ ๋Œ€๋‚˜๋ฌด ์ˆฒ์ด ์žˆ๋‹ค. ํŒ๋‹ค๋Š” ์–ด๋–ค ์ง€์—ญ์—์„œ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋จน๊ธฐ ์‹œ์ž‘ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ๊ณณ์˜ ๋Œ€๋‚˜๋ฌด๋ฅผ ๋‹ค ๋จน์–ด ์น˜์šฐ๋ฉด ์ƒ, ํ•˜, ์ขŒ, ์šฐ ์ค‘ ํ•œ ๊ณณ์œผ๋กœ ์ด๋™์„ ํ•œ๋‹ค. ๊ทธ ์˜ฎ๊ธด ์ง€์—ญ์— ๊ทธ ์ „ ์ง€์—ญ๋ณด๋‹ค ๋Œ€๋‚˜๋ฌด๊ฐ€ ๋งŽ์ด ์žˆ์–ด์•ผ ํ•œ๋‹ค. ์–ด๋–ค ์ง€์ ์— ์ฒ˜์Œ์— ํ’€์–ด ๋†“์•„์•ผ ํ•˜๊ณ , ์–ด๋–ค ๊ณณ์œผ๋กœ ์ด๋™์„ ์‹œ์ผœ์•ผ ํŒ๋‹ค๊ฐ€ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์นธ์„ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ณ ๋ฏผ์— ๋น ์ ธ ์žˆ๋‹ค. ํŒ๋‹ค๊ฐ€ ์ด๋™ํ•  ์ˆ˜ ..
๋ฐฑ์ค€ 15486๋ฒˆ : ํ‡ด์‚ฌ2
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/15486 15486๋ฒˆ: ํ‡ด์‚ฌ 2 ์ฒซ์งธ ์ค„์— N (1 ≤ N ≤ 1,500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— Ti์™€ Pi๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์„œ ์ฃผ์–ด์ง€๋ฉฐ, 1์ผ๋ถ€ํ„ฐ N์ผ๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net ๋ฌธ์ œ ์˜ค๋Š˜๋ถ€ํ„ฐ N+1์ผ์งธ ๋˜๋Š” ๋‚  ํ‡ด์‚ฌ๋ฅผ ํ•˜๊ธฐ ์œ„ํ•ด์„œ, ๋‚จ์€ N์ผ ๋™์•ˆ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์ƒ๋‹ด์„ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๊ฐ๊ฐ์˜ ์ƒ๋‹ด์€ ์ƒ๋‹ด์„ ์™„๋ฃŒํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ๊ธฐ๊ฐ„ Ti์™€ ์ƒ๋‹ด์„ ํ–ˆ์„ ๋•Œ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๊ธˆ์•ก Pi๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ƒ๋‹ด์„ ์ ์ ˆํžˆ ํ–ˆ์„ ๋•Œ, ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ์ˆ˜์ต ๊ตฌํ•˜๊ธฐ ์ œํ•œ์‚ฌํ•ญ N (1 ≤ N ≤ 1,500,000) 1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,00..
๋ฐฑ์ค€ 20440๋ฒˆ : ๐ŸŽต๋‹ˆ๊ฐ€ ์‹ซ์–ด ์‹ซ์–ด ๋„ˆ๋ฌด ์‹ซ์–ด ์‹ซ์–ด ์˜ค์ง€ ๋งˆ ๋‚ด๊ฒŒ ์ฐ์ฉ๋Œ€์ง€๋งˆ๐ŸŽต - 1
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/20440 20440๋ฒˆ: ๐ŸŽต๋‹ˆ๊ฐ€ ์‹ซ์–ด ์‹ซ์–ด ๋„ˆ๋ฌด ์‹ซ์–ด ์‹ซ์–ด ์˜ค์ง€ ๋งˆ ๋‚ด๊ฒŒ ์ฐ์ฉ๋Œ€์ง€๋งˆ๐ŸŽต - 1์ฒซ์งธ ์ค„์— ์ง€๋™์ด์˜ ๋ฐฉ์— ์ถœ์ž…ํ•œ ๋ชจ๊ธฐ์˜ ๋งˆ๋ฆฟ์ˆ˜ N(1 ≤ N ≤ 1,000,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์— ๋ชจ๊ธฐ์˜ ์ž…์žฅ ์‹œ๊ฐ TE๊ณผ ํ‡ด์žฅ ์‹œ๊ฐ TX์ด ์ฃผ์–ด์ง„๋‹ค. (0 ≤ TE www.acmicpc.net      ๋ฌธ์ œ๋ชจ๊ธฐ๋“ค์˜ ๋ฐฉ ์ž…์žฅ, ํ‡ด์žฅ ์‹œ๊ฐ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ๋ชจ๊ธฐ๋“ค์ด ๊ฐ€์žฅ ๋งŽ์ด ์žˆ๋Š” ์‹œ๊ฐ„๋Œ€์™€ ํ•ด๋‹น ์‹œ๊ฐ„๋Œ€์— ๋ชจ๊ธฐ๊ฐ€ ๋ช‡ ๋งˆ๋ฆฌ๊ฐ€ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๊ธฐ ์ œํ•œ ์‚ฌํ•ญ๋ชจ๊ธฐ์˜ ๋งˆ๋ฆฟ์ˆ˜ N(1 ≤ N ≤ 1,000,000)๋ชจ๊ธฐ์˜ ์ž…์žฅ ์‹œ๊ฐ TE๊ณผ ํ‡ด์žฅ ์‹œ๊ฐ TX (0 ≤ TE ≤ 2,100,000,000)๋ชจ๊ธฐ๋Š” [TE, Tx)๋™์•ˆ ์กด์žฌ     ํ’€์ด์ฒ˜์Œ ์ƒ๊ฐ๋‚œ ํ’€์ด๋Š” ์ขŒํ‘œ๊ณ„..
๋ฐฑ์ค€ 1749๋ฒˆ : ์ ์ˆ˜๋”ฐ๋จน๊ธฐ
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/1749 1749๋ฒˆ: ์ ์ˆ˜๋”ฐ๋จน๊ธฐ๋™์ฃผ๋Š” ํ•ญ์ƒ ํ˜ผ์ž ๋…ธ๋Š๋ผ ์‹ฌ์‹ฌํ•˜๋‹ค. ํ•˜์ง€๋งŒ ํ˜ผ์ž ๋†€๊ธฐ์˜ ๊ณ ์ˆ˜๊ฐ€ ๋œ ๋™์ฃผ๋Š” ๋งค์ผ๋งค์ผ ๊ฒŒ์ž„์„ ๊ฐœ๋ฐœํ•˜์—ฌ ํ˜ผ์ž๋†€๊ธฐ์˜ ์ง„์ˆ˜๋ฅผ ์šฐ๋ฆฌ์—๊ฒŒ ๋ณด์—ฌ์ค€๋‹ค. ์–ด๋Š ๋‚  ๋™์ฃผ๋Š” ์ƒˆ๋กœ์šด ๊ฒŒ์ž„์„ ๊ฐœ๋ฐœํ•˜์˜€๋‹ค. ๋ฐ”๋กœ ์ www.acmicpc.net     ๋ฌธ์ œ์ผ๋‹จ N*M ํ–‰๋ ฌ์„ ๊ทธ๋ฆฐ ๋‹ค์Œ, ๊ฐ ์นธ์— -10,000 ์ด์ƒ 10,000 ์ดํ•˜์˜ ์ •์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ์“ด๋‹ค.๊ทธ๋Ÿฐ ๋‹ค์Œ ๊ทธ ํ–‰๋ ฌ์˜ ๋ถ€๋ถ„ํ–‰๋ ฌ์„ ๊ทธ๋ ค ๊ทธ ์•ˆ์— ์ ํžŒ ์ •์ˆ˜์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ๊ฒŒ์ž„์ด๋‹ค.์ •์ˆ˜์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๋ถ€๋ถ„ํ–‰๋ ฌ์„ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค.     ํ’€์ด์ฒ˜์Œ์—๋Š” ์ด์ „์— ํ’€์—ˆ๋˜ '๋ถ€๋ถ„ํ–‰๋ ฌ์—์„œ ๋ถ€๋ถ„ํ•ฉ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ'์˜ ์ ‘๊ทผ๋ฒ•๊ณผ ์œ ์‚ฌํ•˜๊ฒŒ ํ’€์—ˆ๋‹ค. ๋ฐฑ์ค€ 11660๋ฒˆ ๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ5 : https://www.acmic..
๋ฐฑ์ค€ 14846๋ฒˆ : ์ง์‚ฌ๊ฐํ˜•๊ณผ ์ฟผ๋ฆฌ
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/14846 14846๋ฒˆ: ์ง์‚ฌ๊ฐํ˜•๊ณผ ์ฟผ๋ฆฌ ์ฒซ์งธ ์ค„์— N (1 ≤ N ≤ 300)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ํ–‰๋ ฌ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ์ค„์€ N๊ฐœ์˜ ์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ํ–‰์€ ์œ„์—์„œ๋ถ€ํ„ฐ ์•„๋ž˜๋กœ, ์—ด์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ์œผ๋ฉฐ www.acmicpc.net ๋ฌธ์ œ Nํ–‰ N์—ด๋กœ ์ด๋ฃจ์–ด์ง„ ์ •์‚ฌ๊ฐํ˜• ํ–‰๋ ฌ A๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, ์ฟผ๋ฆฌ๋ฅผ ์ˆ˜ํ–‰ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. x1 y1 x2 y2: ์™ผ์ชฝ ์œ—์นธ์ด (x1, y1)์ด๊ณ , ์˜ค๋ฅธ์ชฝ ์•„๋žซ์นธ์ด (x2, y2)์ธ ๋ถ€๋ถ„ ํ–‰๋ ฌ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ์ •์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ œํ•œ์‚ฌํ•ญ ์ฒซ์งธ ์ค„์— N (1 ≤ N ≤ 300)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ํ–‰๋ ฌ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ์ค„์€ N๊ฐœ์˜ ..
giraffe_
'๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก (5 Page)