๋ชฉ๋ก๐Ÿ‘Š PS (125)

hades

[Baekjoon] 7662๋ฒˆ: ์ด์ค‘ ์šฐ์„ ์ˆœ์œ„ ํ

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/7662 ๐Ÿ” ์„ค๊ณ„์ฒ˜์Œ์— min_pq์™€ max_pq๋งŒ์„ ๋งŒ๋“ค์–ด์„œ D์ผ ๋•Œ n์ด ๋ฌด์—‡์ด๋ƒ์— ๋”ฐ๋ผ ํ•œ์ชฝ์œผ๋กœ ๋ชฐ์•„์„œ ์ฒ˜๋ฆฌํ•˜๋Š” ๋ฐฉ์‹์„ ํƒํ–ˆ๋Š”๋ฐ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค. ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ฐพ์•„์•ผ ํ•œ๋‹ค. map์„ ์ด์šฉํ•˜์—ฌ ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•˜๊ณ , D์ผ ๋•Œ, ์‚ญ์ œ๋ฅผ ํ•˜๊ธฐ ์ „, ๋‹ค๋ฅธ ๋ช…๋ น์—์„œ ๊ฐœ์ˆ˜๊ฐ€ 0์ด ๋˜์—ˆ์„ ์ˆ˜๋„ ์žˆ์œผ๋ฏ€๋กœ ๊ทธ ๊ฒฝ์šฐ๋ฅผ ๊ณ ๋ คํ•˜์—ฌ ์‚ญ์ œ ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด D 1์ด์–ด์„œ max_pq์—์„œ๋Š” ์‚ญ์ œํ–ˆ์ง€๋งŒ, min_pq์—์„œ๋Š” ์‚ญ์ œํ•  ์ˆ˜ ์—†์œผ๋ฏ€๋กœ ๋ฐ˜์˜๋˜์ง€ ์•Š์•˜๋‹ค. ๊ฐœ์ˆ˜๋งŒ ๊ฐ์†Œ์‹œํ‚ค๊ณ , ์‚ญ์ œํ•˜๋ ค๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ 0์ผ ๋•Œ, ๋ชจ๋‘ ์‚ญ์ œํ•œ๋‹ค. ๐Ÿ‘Š ํ’€์ด#include #include #include using namespace std;char ch;int t, ..

๐Ÿ‘Š PS/Algorithm 2024. 7. 17. 22:42
[Baekjoon] 7569๋ฒˆ: ํ† ๋งˆํ† 

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/7569 ๐Ÿ” ์„ค๊ณ„์ต์€ ํ† ๋งˆํ† ๊ฐ€ ์ธ์ ‘ํ•œ ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ์— ์˜ํ–ฅ์„ ์ค€๋‹ค. BFS ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์„ ์•Œ์•„์ฐจ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ์ฒ˜์Œ์— ์ต์€ ํ† ๋งˆํ† ๋ฅผ ํ์— ๋‹ด๋Š”๋‹ค. ๋‚ ๋งˆ๋‹ค ์ต์€ ํ† ๋งˆํ† ์˜ ์˜ํ–ฅ๋ ฅ์„ ํ–‰์‚ฌํ•œ๋‹ค. ์ฃผ๋ณ€์˜ ํ† ๋งˆํ† ๊ฐ€ ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๋ผ๋ฉด, ์ต๊ฒŒ ๋งŒ๋“ค๊ณ , ๊ทธ ํ† ๋งˆํ† ๋ฅผ ํ์— ๋‹ด๋Š”๋‹ค. ์ฃผ์˜ํ•ด์•ผํ•  ๊ฒƒ์€ ๋‚ ๋งˆ๋‹ค ์ต์€ ํ† ๋งˆํ† ์˜ ์˜ํ–ฅ๋ ฅ์„ ํ–‰์‚ฌํ–ˆ๋Š”๋ฐ, ์˜ํ–ฅ์„ ๋ฐ›์€ ํ† ๋งˆํ† ๊ฐ€ ์—†๋‹ค๋ฉด, day๋ฅผ ์ฆ๊ฐ€์‹œํ‚ค๋ฉด ์•ˆ๋œ๋‹ค. ๐Ÿ‘Š ํ’€์ด#include #include using namespace std;int dh[] = { -1,1,0,0,0,0 };int dl[] = { 0,0,0,0, -1,1 };int dw[] = { 0,0,-1,1,0,0 };int m, n, h, da..

๐Ÿ‘Š PS/Algorithm 2024. 7. 16. 19:52
[Baekjoon] 5430๋ฒˆ: AC

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/5430 ๐Ÿ” ์„ค๊ณ„R์ด๋ฉด ๋’ค์ง‘๊ณ , D์ด๋ฉด ๋งจ ์•ž์— ์žˆ๋Š” ์ˆซ์ž๋ฅผ ์‚ญ์ œํ•ด์•ผ ํ•˜๋Š”๋ฐ, R์ผ ๋•Œ๋งˆ๋‹ค ๋’ค์ง‘๋Š”๋ฐ ์‹œ๊ฐ„์ด ๋งŽ์ด ์†Œ์š”๋œ๋‹ค.๋”ฐ๋ผ์„œ, ์•ž ๋’ค์—์„œ ์‚ญ์ œ๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฑ์„ ์ด์šฉํ•œ๋‹ค. ์ž…๋ ฅ์— ๊ด„ํ˜ธ์™€ ์‰ผํ‘œ๊ฐ€ ํฌํ•จ๋˜์–ด ์ž…๋ ฅ๋˜๋ฏ€๋กœ, ์กฐ๊ฑด๋ฌธ์„ ํ†ตํ•ด ์ˆซ์ž๋“ค์„ ๋‹ด์•„์•ผ ํ•œ๋‹ค.[ ๋ผ๋ฉด ์ถ”๊ฐ€์ ์ธ ์ฒ˜๋ฆฌ๋ฅผ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค., ๋˜๋Š” ] ๋ผ๋ฉด ์ˆซ์ž๋ฅผ ๋ฑ์— ๋‹ด๋Š”๋‹ค.์ด์™ธ๋ผ๋ฉด, ์ˆซ์ž๋ฅผ ๊ตฌ์„ฑํ•œ๋‹ค. ์ถœ๋ ฅ, ์‚ญ์ œํ•  ๋•Œ ์•ž์—์„œ๋ถ€ํ„ฐ ํ• ์ง€ ๋’ค์—์„œ๋ถ€ํ„ฐ ํ• ์ง€ ๊ฒฐ์ •ํ•˜๊ธฐ ์œ„ํ•ด sign์ด๋ผ๋Š” ๋ณ€์ˆ˜๋ฅผ ์„ค์ •ํ•˜์˜€๋‹ค. 0์ด๋ฉด ์•ž์—์„œ๋ถ€ํ„ฐ, 1์ด๋ฉด ๋’ค์—์„œ๋ถ€ํ„ฐ, 2์ด๋ฉด ๋น„์–ด์žˆ๋Š”๋ฐ ์‚ญ์ œํ•ด์„œ error์ธ ๊ฒฝ์šฐ์ด๋‹ค. ๐Ÿ‘Š ํ’€์ด#include #include #include using namespace std;..

๐Ÿ‘Š PS/Algorithm 2024. 7. 15. 10:08
[Baekjoon] 2630๋ฒˆ: ์ƒ‰์ข…์ด ๋งŒ๋“ค๊ธฐ

๐Ÿฅ… ๋ฌธ์ œhttps://www.acmicpc.net/problem/2630 ๐Ÿ” ์„ค๊ณ„ํ˜„์žฌ ์ƒ‰์ข…์ด์˜ ๋ชจ๋“  ์นธ์˜ ์ƒ‰์ด ๊ฐ™์ง€ ์•Š์œผ๋ฉด 4๋“ฑ๋ถ„ํ•ด ๋‚˜๊ฐ€๋Š” ๋ฌธ์ œ์ด๋‹ค. ์žฌ๊ท€๋กœ ํ•ด๊ฒฐํ•  ๋•Œ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด๋ฉด, O(2^7*2^7+2^6*2^6*2^2+2^5*2^5*2^2*2^2...)=O(2^14*8)=O(2^17)์ด๋ฏ€๋กœ, ์‹œ๊ฐ„ ์ œํ•œ 1์ดˆ ๋‚ด์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ์žฌ๊ท€ํ•จ์ˆ˜์— ์‹œ์ž‘์ ๊ณผ ํ˜„์žฌ ์ƒ‰์ข…์ด์˜ ๋ณ€์˜ ๊ธธ์ด๋ฅผ ์ „๋‹ฌํ•œ๋‹ค. ์นธ์˜ ์ƒ‰์ด ํ•˜๋‚˜๋ผ๋„ ๋‹ค๋ฅด๋ฉด ์ž˜๋ผ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋น„๊ต ๋Œ€์ƒ์€ ์‹œ์ž‘์ ์˜ ์ƒ‰์œผ๋กœ ํ•˜์˜€๋‹ค.  ํ˜„์žฌ ์ƒ‰์ข…์ด์˜ ๋ชจ๋“  ์นธ์„ ํ™•์ธํ•˜๋ฉด์„œ ๋‹ค๋ฅธ ์ƒ‰์„ ๊ฐ€์ง„ ์นธ์ด ์žˆ๋‹ค๋ฉด, 4๋“ฑ๋ถ„ํ•œ ์ƒ‰์ข…์ด๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰ํ•œ๋‹ค. ํ˜„์žฌ ์ƒ‰์ข…์ด์˜ ๋ชจ๋“  ์นธ์„ ํ™•์ธํ•˜๋ฉด์„œ ๋‹ค๋ฅธ ์ƒ‰์„ ๊ฐ€์ง„ ์นธ์ด ์—†๋‹ค๋ฉด, ์‹œ์ž‘์ ์˜ ์ƒ‰๊ณผ ๋ชจ๋‘ ๊ฐ™๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€..

๐Ÿ‘Š PS/Algorithm 2024. 7. 11. 18:13