๋ฐฑ์ค€

    [BOJ_4574] ์Šค๋„๋ฏธ๋…ธ์ฟ  (java)

    [BOJ_4574] ์Šค๋„๋ฏธ๋…ธ์ฟ  (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/4574 4574๋ฒˆ: ์Šค๋„๋ฏธ๋…ธ์ฟ  ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์—๋Š” ์ฑ„์›Œ์ ธ ์žˆ๋Š” ๋„๋ฏธ๋…ธ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (10 ≤ N ≤ 35) ๋‹ค์Œ N๊ฐœ ์ค„์—๋Š” ๋„๋ฏธ๋…ธ ํ•˜๋‚˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” U LU V LV๊ฐ€ www.acmicpc.net ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ์žฌ๊ท€, ๋ธŒ๋ฃจํŠธํฌ์Šค, ๋ฐฑํŠธ๋ž˜ํ‚น ์Šค๋„๋ฏธ๋…ธ์ฟ ๋Š” ์Šค๋„์ฟ  + ๋„๋ฏธ๋…ธ๋ฅผ ์˜๋ฏธํ•˜๋Š” ๊ฒŒ์ž„์ด๋‹ค. ์Šค๋„์ฟ ์˜ ๊ทœ์น™์„ ์ง€์ผœ์ฃผ๋ฉฐ, ๋„๋ฏธ๋…ธ(2๊ฐœ์˜ ์Œ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ฐ’)์„ ๋†“์•„์ฃผ์–ด ์Šค๋„์ฟ ๋ฅผ ํ’€์–ด์ฃผ๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋„๋ฏธ๋…ธ๋Š” $(1,2), (1,3) (1,4) ... (7,8) (7,9) (8,9)$ ๊นŒ์ง€ 1๋ถ€ํ„ฐ 9๊นŒ์ง€์˜ ๋ชจ๋“  ๊ฐ’์˜ ์Œ์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ $(1..

    [BOJ_16197] ๋‘ ๋™์ „ (java)

    [BOJ_16197] ๋‘ ๋™์ „ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/16197 16197๋ฒˆ: ๋‘ ๋™์ „ N×M ํฌ๊ธฐ์˜ ๋ณด๋“œ์™€ 4๊ฐœ์˜ ๋ฒ„ํŠผ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ฒŒ์ž„์ด ์žˆ๋‹ค. ๋ณด๋“œ๋Š” 1×1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๊ณ , ๊ฐ๊ฐ์˜ ์นธ์€ ๋น„์–ด์žˆ๊ฑฐ๋‚˜, ๋ฒฝ์ด๋‹ค. ๋‘ ๊ฐœ์˜ ๋นˆ ์นธ์—๋Š” ๋™์ „์ด ํ•˜๋‚˜์”ฉ ๋†“์—ฌ์ ธ ์žˆ๊ณ , www.acmicpc.net ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ๋ธŒ๋ฃจํŠธํฌ์Šค, ์žฌ๊ท€ ๋ฌธ์ œ๋Š” ๋‘ ๋™์ „์„ ๋ณด๋“œํŒ์— ์˜ฌ๋ ค๋†“๊ณ  ์ƒํ•˜์ขŒ์šฐ ์ค‘ ํ•œ ๊ณณ์œผ๋กœ ์ด๋™์‹œ์ผœ ์ฃผ์–ด ํ•˜๋‚˜์˜ ๋™์ „๋งŒ ๋–จ์–ด๋œจ๋ฆฌ๋Š” ๋ฐฉ๋ฒ•์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋‹จ, ๋™์ „์ด ์›€์ง์ผ ๋•Œ ๋ฒฝ์„ ๋งŒ๋‚˜๊ฒŒ ๋˜๋ฉด ์›€์ง์ด์ง€ ๋ชปํ•˜๋ฉฐ, ๊ทธ ์™ธ์˜ ๊ฒฝ์šฐ์—๋Š” ๋ชจ๋‘ ์›€์ง์—ฌ ์ค„ ์ˆ˜ ์žˆ๋‹ค. ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ๋Š” ๋™์ „์ด ๋ณด๋“œ์˜ ๋ฐฐ์—ด ๋ฐ–์œผ๋กœ ๋‚˜๊ฐ€๋Š”(๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋Š”) ๊ฒฝ์šฐ๊ฐ€ ๋œ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ๋ธŒ๋ฃจํŠธํฌ์Šค๋กœ ..

    BOJ_14888 ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ (Java)

    BOJ_14888 ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ (Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/14888 14888๋ฒˆ: ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(2 ≤ N ≤ 11)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” A1, A2, ..., AN์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Ai ≤ 100) ์…‹์งธ ์ค„์—๋Š” ํ•ฉ์ด N-1์ธ 4๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ฐจ๋ก€๋Œ€๋กœ ๋ง์…ˆ(+)์˜ ๊ฐœ์ˆ˜, ๋บ„์…ˆ(-)์˜ ๊ฐœ์ˆ˜, www.acmicpc.net ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ๋ธŒ๋ฃจํŠธํฌ์Šค ์—ฐ์‚ฐ์ž๋ฅผ ๋ผ์›Œ ๋„ฃ๋Š” ๋ฌธ์ œ๋Š” ๋ธŒ๋ฃจํŠธํฌ์Šค๋กœ ํ•ด๊ฒฐํ•˜์˜€๋‹ค. ์—ฐ์‚ฐ์ž์˜ ๊ฐœ์ˆ˜๋Š” ์ˆซ์ž ๋ฐฐ์—ด์˜ ํฌ๊ธฐ -1 ์ด๋ฏ€๋กœ ์ตœ๋Œ€ 10๊ฐœ์ด๋‹ค. 10๊ฐœ๋ฅผ ์ˆœ์„œ๋ฅผ ๊ณ ๋ คํ•˜์—ฌ ๋‚˜์—ดํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์ตœ๋Œ€ 10!์ด๋ฏ€๋กœ ์‹œ๊ฐ„์ดˆ๊ณผ ์—†์ด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ, ๋งŒ๋“ค์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์—ฐ์‚ฐ์ž์˜ ๊ฒฝ์šฐ์˜์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด์ค€ ๋’ค ๊ณ„์‚ฐํ•ด ์ฃผ๋ฉด ์‰ฝ๊ฒŒ ํ•ด..

    [BOJ_16931] ๊ฒ‰๋„“์ด ๊ตฌํ•˜๊ธฐ (java)

    [BOJ_16931] ๊ฒ‰๋„“์ด ๊ตฌํ•˜๊ธฐ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/16931 16931๋ฒˆ: ๊ฒ‰๋„“์ด ๊ตฌํ•˜๊ธฐ ํฌ๊ธฐ๊ฐ€ N×M์ธ ์ข…์ด๊ฐ€ ์žˆ๊ณ , ์ข…์ด๋Š” 1×1ํฌ๊ธฐ์˜ ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค. ์ด ์ข…์ด์˜ ๊ฐ ์นธ ์œ„์— 1×1×1 ํฌ๊ธฐ์˜ ์ •์œก๋ฉด์ฒด๋ฅผ ๋†“์•„ 3์ฐจ์› ๋„ํ˜•์„ ๋งŒ๋“ค์—ˆ๋‹ค. ์ข…์ด์˜ ๊ฐ ์นธ์— ๋†“์ธ ์ •์œก๋ฉด์ฒด์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด www.acmicpc.net ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ์‹œ๋ฎฌ๋ ˆ์ด์…˜, ๊ตฌํ˜„ ๊ฒ‰๋„“์ด๋ฅผ ๋ชจ๋‘ ๊ตฌํ•ด์ฃผ๋Š” ๋ฌธ์ œ์ด๋‹ค. ์œ—๋ฉด๊ณผ ์•„๋žซ๋ฉด ๊ทธ๋ฆฌ๊ณ  ์˜†๋ฉด์œผ๋กœ ๋‚˜๋ˆ„์–ด ๊ตฌํ˜„์„ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค. ์œ—๋ฉด๊ณผ ์•„๋žซ๋ฉด ์œ—๋ฉด๊ณผ ์•„๋žซ๋ฉด์˜ ๊ฒ‰๋„“์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋งค์šฐ ๊ฐ„๋‹จํ•˜๋‹ค. ์กฐ๊ฑด์—์„œ ์ฃผ์–ด์ง„ $n*m$์— ๋ธ”๋Ÿญ์ด 1๊ฐœ ์ด์ƒ ๋“ค์–ด๊ฐ€์•ผํ•˜๋ฏ€๋กœ ํ•ญ์ƒ ๋„“์ด๋Š” $n*m$์ด ๋œ๋‹ค. ์˜†๋ฉด ์˜†๋ฉด์˜ ๋„“์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์€ 4๋ฐฉ๋ฉด์œผ๋กœ ๋ถ™์–ด์žˆ๋Š” ๋„ํ˜•์„ ํ™•์ธํ•˜..

    [BOJ_15685] ๋“œ๋ž˜๊ณค ์ปค๋ธŒ (Java)

    [BOJ_15685] ๋“œ๋ž˜๊ณค ์ปค๋ธŒ (Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/15685 15685๋ฒˆ: ๋“œ๋ž˜๊ณค ์ปค๋ธŒ ์ฒซ์งธ ์ค„์— ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 20)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๋Š” ๋„ค ์ •์ˆ˜ x, y, d, g๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. x์™€ y๋Š” ๋“œ๋ž˜๊ณค ์ปค www.acmicpc.net ๋ฌธ์ œํ’€์ด ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ํ•ต์‹ฌ ์Šคํ‚ฌ ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋“œ๋ž˜๊ณค์ปค๋ธŒ ๋ฌธ์ œ๋ฅผ ๋ดค์„ ๋•Œ ๊ต‰์žฅํžˆ ๋‚œํ•ดํ•˜๋‹ค๋Š” ์ƒ๊ฐ์„ ๋ฐ›์•˜์—ˆ์Šต๋‹ˆ๋‹ค. ์–ด๋–ป๊ฒŒ ๊ทธ๋ž˜ํ”„๋ฅผ ํŠน์ • ์ ์—์„œ 90๋„์”ฉ ๋Œ๋ฆด ์ˆ˜ ์žˆ์„๊นŒ ๊ณ ๋ฏผ์„ ๋งŽ์ด ํ–ˆ๋Š”๋ฐ, ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆด ๋•Œ ํ•ด๋‹น ์ ์—์„œ ์–ด๋Š ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜์˜€๋Š”์ง€๋งŒ ์•Œ๋ฉด ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ ๋ฌธ์ œ๋Š” ํŠน์ • ์‹œ์ž‘ ์ ์—์„œ ์‹œ์ž‘ ๋ฐฉํ–ฅ์œผ๋กœ 1์นธ ์ด๋™ํ•˜..

    [BOJ_14499] ์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ (java)

    [BOJ_14499] ์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/14499 14499๋ฒˆ: ์ฃผ์‚ฌ์œ„ ๊ตด๋ฆฌ๊ธฐ ์ฒซ์งธ ์ค„์— ์ง€๋„์˜ ์„ธ๋กœ ํฌ๊ธฐ N, ๊ฐ€๋กœ ํฌ๊ธฐ M (1 ≤ N, M ≤ 20), ์ฃผ์‚ฌ์œ„๋ฅผ ๋†“์€ ๊ณณ์˜ ์ขŒํ‘œ x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), ๊ทธ๋ฆฌ๊ณ  ๋ช…๋ น์˜ ๊ฐœ์ˆ˜ K (1 ≤ K ≤ 1,000)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ง€ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ํฌ๊ธฐ๊ฐ€ N×M์ธ ์ง€๋„๊ฐ€ ์กด์žฌํ•œ๋‹ค. ์ง€๋„์˜ ์˜ค๋ฅธ์ชฝ์€ ๋™์ชฝ, ์œ„์ชฝ์€ ๋ถ์ชฝ์ด๋‹ค. ์ด ์ง€๋„์˜ ์œ„์— ์ฃผ์‚ฌ์œ„๊ฐ€ ํ•˜๋‚˜ ๋†“์—ฌ์ ธ ์žˆ์œผ๋ฉฐ, ์ฃผ์‚ฌ์œ„์˜ ์ „๊ฐœ๋„๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค. ์ง€๋„์˜ ์ขŒํ‘œ๋Š” (r, c)๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, r๋Š” ๋ถ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜, c๋Š” ์„œ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค. 2 4 1 3 5..

    [BOJ_2667] ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ (java)

    [BOJ_2667] ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/2667 2667๋ฒˆ: ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ ๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์—ฐ๊ฒฐ๋˜์—ˆ๋‹ค๋Š” ๊ฒƒ์€ ์–ด๋–ค ์ง‘์ด ์ขŒ์šฐ, ํ˜น์€ ์•„๋ž˜์œ„๋กœ ๋‹ค๋ฅธ ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ๋งํ•œ๋‹ค. ๋Œ€๊ฐ์„ ์ƒ์— ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—ฐ๊ฒฐ๋œ ๊ฒƒ์ด ์•„๋‹ˆ๋‹ค. ๋Š” ์„ ๋‹จ์ง€๋ณ„๋กœ ๋ฒˆํ˜ธ๋ฅผ ..

    [backjoon_11057] ์˜ค๋ฅด๋ง‰ ์ˆ˜ (Java)

    [backjoon_11057] ์˜ค๋ฅด๋ง‰ ์ˆ˜ (Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/11057 11057๋ฒˆ: ์˜ค๋ฅด๋ง‰ ์ˆ˜ ์˜ค๋ฅด๋ง‰ ์ˆ˜๋Š” ์ˆ˜์˜ ์ž๋ฆฌ๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์„ ์ด๋ฃจ๋Š” ์ˆ˜๋ฅผ ๋งํ•œ๋‹ค. ์ด๋•Œ, ์ธ์ ‘ํ•œ ์ˆ˜๊ฐ€ ๊ฐ™์•„๋„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์นœ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 2234์™€ 3678, 11119๋Š” ์˜ค๋ฅด๋ง‰ ์ˆ˜์ด์ง€๋งŒ, 2232, 3676, 91111์€ ์˜ค๋ฅด๋ง‰ ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋‹ค. ์ˆ˜ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์˜ค๋ฅด๋ง‰ ์ˆ˜๋Š” ์ˆ˜์˜ ์ž๋ฆฌ๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์„ ์ด๋ฃจ๋Š” ์ˆ˜๋ฅผ ๋งํ•œ๋‹ค. ์ด๋•Œ, ์ธ์ ‘ํ•œ ์ˆ˜๊ฐ€ ๊ฐ™์•„๋„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์นœ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 2234์™€ 3678, 11119๋Š” ์˜ค๋ฅด๋ง‰ ์ˆ˜์ด์ง€๋งŒ, 2232, 3676, 91111์€ ์˜ค๋ฅด๋ง‰ ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋‹ค. ์ˆ˜์˜ ๊ธธ์ด N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ˆ˜๋Š” 0์œผ๋กœ ์‹œ์ž‘ํ•  ์ˆ˜..

    [backjoon_2225] ํ•ฉ๋ถ„ํ•ด (Java)

    [backjoon_2225] ํ•ฉ๋ถ„ํ•ด (Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/2225 2225๋ฒˆ: ํ•ฉ๋ถ„ํ•ด ์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ 0๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ์ •์ˆ˜ K๊ฐœ๋ฅผ ๋”ํ•ด์„œ ๊ทธ ํ•ฉ์ด N์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋ง์…ˆ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€ ๊ฒฝ์šฐ๋Š” ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋กœ ์„ผ๋‹ค(1+2์™€ 2+1์€ ์„œ๋กœ ๋‹ค๋ฅธ ๊ฒฝ์šฐ). ๋˜ํ•œ ํ•œ ๊ฐœ์˜ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์“ธ ์ˆ˜๋„ ์žˆ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ œํ•œ์‚ฌํ•ญ ์ œํ•œ์‹œ๊ฐ„ ๋ฉ”๋ชจ๋ฆฌ์ œํ•œ 2์ดˆ 128MB * ์ถœ์ฒ˜ : https://www.acmicpc.ne..

    [backjoon_15990] 1,2,3 ๋”ํ•˜๊ธฐ 5(Java)

    [backjoon_15990] 1,2,3 ๋”ํ•˜๊ธฐ 5(Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/15990 15990๋ฒˆ: 1, 2, 3 ๋”ํ•˜๊ธฐ 5 ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค, n์„ 1, 2, 3์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ 1,000,000,009๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์ •์ˆ˜ 4๋ฅผ 1, 2, 3์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•์€ ์ด 3๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. ํ•ฉ์„ ๋‚˜ํƒ€๋‚ผ ๋•Œ๋Š” ์ˆ˜๋ฅผ 1๊ฐœ ์ด์ƒ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค. ๋‹จ, ๊ฐ™์€ ์ˆ˜๋ฅผ ๋‘ ๋ฒˆ ์ด์ƒ ์—ฐ์†ํ•ด์„œ ์‚ฌ์šฉํ•˜๋ฉด ์•ˆ ๋œ๋‹ค. 1+2+1 1+3 3+1 ์ •์ˆ˜ n์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, n์„ 1, 2, 3์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , ..

    [Backjoon_11052] ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ(Java)

    [Backjoon_11052] ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ(Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/11052 11052๋ฒˆ: ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ๋ฏผ๊ทœ๊ฐ€ ๊ตฌ๋งคํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000) ๋‘˜์งธ ์ค„์—๋Š” Pi๊ฐ€ P1๋ถ€ํ„ฐ PN๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์š”์ฆ˜ ๋ฏผ๊ทœ๋„ค ๋™๋„ค์—์„œ๋Š” ์Šคํƒ€ํŠธ๋งํฌ์—์„œ ๋งŒ๋“  PS์นด๋“œ๋ฅผ ๋ชจ์œผ๋Š” ๊ฒƒ์ด ์œ ํ–‰์ด๋‹ค. PS์นด๋“œ๋Š” PS(Problem Solving)๋ถ„์•ผ์—์„œ ์œ ๋ช…ํ•œ ์‚ฌ๋žŒ๋“ค์˜ ์•„์ด๋””์™€ ์–ผ๊ตด์ด ์ ํ˜€์žˆ๋Š” ์นด๋“œ์ด๋‹ค. ๊ฐ๊ฐ์˜ ์นด๋“œ์—๋Š” ๋“ฑ๊ธ‰์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ƒ‰์ด ์น ํ•ด์ ธ ์žˆ๊ณ , ๋‹ค์Œ๊ณผ ๊ฐ™์ด 8๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. ์ „์„ค์นด๋“œ ๋ ˆ๋“œ์นด๋“œ ์˜ค๋ Œ์ง€์นด๋“œ ํผํ”Œ์นด๋“œ ๋ธ”๋ฃจ์นด๋“œ ์ฒญ๋ก์นด๋“œ ๊ทธ๋ฆฐ์นด๋“œ ๊ทธ๋ ˆ์ด์นด๋“œ ์นด๋“œ๋Š” ์นด๋“œํŒฉ์˜ ํ˜•ํƒœ๋กœ๋งŒ ๊ตฌ๋งคํ• ..

    [Backjoon_14391] ์ข…์ด์กฐ๊ฐ (Java)

    [Backjoon_14391] ์ข…์ด์กฐ๊ฐ (Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/14391 ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์˜์„ ์ด๋Š” ์ˆซ์ž๊ฐ€ ์“ฐ์—ฌ ์žˆ๋Š” ์ง์‚ฌ๊ฐํ˜• ์ข…์ด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ข…์ด๋Š” 1×1 ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๊ณ , ์ˆซ์ž๋Š” ๊ฐ ์นธ์— ํ•˜๋‚˜์”ฉ ์“ฐ์—ฌ ์žˆ๋‹ค. ํ–‰์€ ์œ„์—์„œ๋ถ€ํ„ฐ ์•„๋ž˜๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๊ณ , ์—ด์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค. ์˜์„ ์ด๋Š” ์ง์‚ฌ๊ฐํ˜•์„ ๊ฒน์น˜์ง€ ์•Š๋Š” ์กฐ๊ฐ์œผ๋กœ ์ž๋ฅด๋ ค๊ณ  ํ•œ๋‹ค. ๊ฐ ์กฐ๊ฐ์€ ํฌ๊ธฐ๊ฐ€ ์„ธ๋กœ๋‚˜ ๊ฐ€๋กœ ํฌ๊ธฐ๊ฐ€ 1์ธ ์ง์‚ฌ๊ฐํ˜• ๋ชจ์–‘์ด๋‹ค. ๊ธธ์ด๊ฐ€ N์ธ ์กฐ๊ฐ์€ N์ž๋ฆฌ ์ˆ˜๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ฐ€๋กœ ์กฐ๊ฐ์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ๊นŒ์ง€ ์ˆ˜๋ฅผ ์ด์–ด ๋ถ™์ธ ๊ฒƒ์ด๊ณ , ์„ธ๋กœ ์กฐ๊ฐ์€ ์œ„์—์„œ๋ถ€ํ„ฐ ์•„๋ž˜๊นŒ์ง€ ์ˆ˜๋ฅผ ์ด์–ด๋ถ™์ธ ๊ฒƒ์ด๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ 4×4 ํฌ๊ธฐ์˜ ์ข…์ด๋ฅผ ์ž๋ฅธ ํ•œ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด๋‹ค. ๊ฐ ์กฐ๊ฐ์˜ ํ•ฉ์€ 4..

    [Backjoon_1182] ๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ(Java)

    [Backjoon_1182] ๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ(Java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/1182 1182๋ฒˆ: ๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ ์ฒซ์งธ ์ค„์— ์ •์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” N๊ณผ ์ •์ˆ˜ S๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) ๋‘˜์งธ ์ค„์— N๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์–ด์ง€๋Š” ์ •์ˆ˜์˜ ์ ˆ๋Œ“๊ฐ’์€ 100,000์„ ๋„˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ N๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ์ˆ˜์—ด์ด ์žˆ์„ ๋•Œ, ํฌ๊ธฐ๊ฐ€ ์–‘์ˆ˜์ธ ๋ถ€๋ถ„์ˆ˜์—ด ์ค‘์—์„œ ๊ทธ ์ˆ˜์—ด์˜ ์›์†Œ๋ฅผ ๋‹ค ๋”ํ•œ ๊ฐ’์ด S๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ •์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” N๊ณผ ์ •์ˆ˜ S๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) ๋‘˜์งธ ์ค„์— N๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ..

    [Backjoon_10971] ์™ธํŒ์› ์ˆœํšŒ 2

    [Backjoon_10971] ์™ธํŒ์› ์ˆœํšŒ 2

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/10971 10971๋ฒˆ: ์™ธํŒ์› ์ˆœํšŒ 2 ์ฒซ์งธ ์ค„์— ๋„์‹œ์˜ ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (2 ≤ N ≤ 10) ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” ๋น„์šฉ ํ–‰๋ ฌ์ด ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ–‰๋ ฌ์˜ ์„ฑ๋ถ„์€ 1,000,000 ์ดํ•˜์˜ ์–‘์˜ ์ •์ˆ˜์ด๋ฉฐ, ๊ฐˆ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ๋Š” 0์ด ์ฃผ์–ด์ง„๋‹ค. W[i][j]๋Š” ๋„์‹œ i์—์„œ j www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ์™ธํŒ์› ์ˆœํšŒ ๋ฌธ์ œ๋Š” ์˜์–ด๋กœ Traveling Salesman problem (TSP) ๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” ๋ฌธ์ œ๋กœ computer science ๋ถ„์•ผ์—์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•˜๊ฒŒ ์ทจ๊ธ‰๋˜๋Š” ๋ฌธ์ œ ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๋ณ€์ข… ๋ฌธ์ œ๊ฐ€ ์žˆ์œผ๋‚˜, ์—ฌ๊ธฐ์„œ๋Š” ๊ฐ€์žฅ ์ผ๋ฐ˜์ ์ธ ํ˜•ํƒœ์˜ ๋ฌธ์ œ๋ฅผ ์‚ดํŽด๋ณด์ž. 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋Š” ๋„์‹œ๋“ค์ด ์žˆ..

    [Backjoon_4375] 1 (Java)

    [Backjoon_4375] 1 (Java)

    ๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/4375 4375๋ฒˆ: 1 2์™€ 5๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ์ •์ˆ˜ n(1 ≤ n ≤ 10000)๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. www.acmicpc.net ๋ฌธ์ œ ์š”์•ฝ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ 2์™€ 5๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ์ •์ˆ˜ n(1 ≤ n ≤ 10000)๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•œ๋‹ค. ์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , n์ด ์ฃผ์–ด์ง„๋‹ค. 1๋กœ ์ด๋ฃจ์–ด์ง„ n์˜ ๋ฐฐ์ˆ˜ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ์ˆ˜์˜ ์ž๋ฆฌ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์‹œ๊ฐ„ ์ œํ•œ 1์ดˆ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ 128MB ๋ฌธ์ œ ํ’€์ด n์„ ์ž…๋ ฅ๋ฐ›์•„ n์˜ ๋ฐฐ์ˆ˜์ค‘ 1๋กœ๋งŒ ์ด๋ฃจ์–ด์ง„ ๊ฐ€์žฅ ์ž‘์€..

    ๋ธŒ๋ฃจํŠธํฌ์Šค(1) - ๋ฌด์ž‘์ • ํ•ด๋ณด๊ธฐ

    ๋ธŒ๋ฃจํŠธํฌ์Šค(1) - ๋ฌด์ž‘์ • ํ•ด๋ณด๊ธฐ

    ๋ธŒ๋ฃจํŠธ ํฌ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํ•ด๋ณด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋ฌด์ž‘์ • ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ ค ๊ตฌํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ๋ธŒ๋ฃจํŠธํฌ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์˜ˆ์‹œ ๋ฌธ์ œ : n์ด ์ฃผ์–ด์กŒ์„๋•Œ, 1๋ถ€ํ„ฐ n ์ค‘์— 2์˜ ๋ฐฐ์ˆ˜์˜ ์ˆ˜๋Š”? (1

    ์ตœ๋Œ€, ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜ ๊ทธ๋ฆฌ๊ณ  ์†Œ์ˆ˜

    ์ตœ๋Œ€, ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜ ๊ทธ๋ฆฌ๊ณ  ์†Œ์ˆ˜

    ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD) ๋‘ ์ˆ˜ a,b์˜ ๊ณตํ†ต๋œ ์•ฝ์ˆ˜์ค‘ ๊ฐ€์žฅ ํฐ ์ˆ˜ - ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ• 1. 2๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ a,b๋กœ ๊ณตํ†ต๋˜๊ฒŒ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ๊ฒƒ์ค‘ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•œ๋‹ค. O(n) -> n์€ a,b์ค‘ ์ตœ์†Œ๊ฐ’ 2. ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ•์„ ์‚ฌ์šฉํ•˜๊ธฐ // ๋‚˜๋Š” ์ฃผ๋กœ ์žฌ๊ท€๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ํŽธ public int gcd(int a, int b){ if(a%b == 0) return b; return gcd(a,a%b); } //๋ฐ˜๋ณต๋ฌธ์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ• ์ˆ˜๋„ ์žˆ์Œ public int gcd(int a, int b){ int temp; while(true){ if(a%b == 0) return b; temp = a % b; a = b; b = temp; } } ์œ„ ์ฝ”๋“œ๋Š” ์œ ํด๋ฆฌ๋“œ ํ˜ธ์žฌ๋ฒ•์„ ์‚ฌ์šฉํ•ด์„œ ๊ตฌํ˜„ํ•ด๋ณธ ์ฝ”๋“œ์ด๋‹ค. ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(LCM) - ์ตœ์†Œ..

    ์•ฝ์ˆ˜

    ์•ฝ์ˆ˜

    ์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ• 1. 1๋ถ€ํ„ฐ n๊นŒ์ง€ %์—ฐ์‚ฐ์„ ํ™œ์šฉํ•˜์—ฌ ๊ตฌํ•˜๊ธฐ 2. 1๋ถ€ํ„ฐ ๋ฃจํŠธn๊นŒ์ง€ %์—ฐ์‚ฐ์„ ํ™œ์šฉํ•˜์—ฌ ๊ตฌํ•˜๊ธฐ ๋ฃจํŠธn๊นŒ์ง€๋งŒ ๋น„๊ตํ•ด๋„ ๋˜๋Š” ์ด์œ ๋Š” ์•ฝ์ˆ˜๋Š” ์ง์„ ์ง€์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์•ฝ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ ํ™€์ˆ˜์ผ ๊ฒฝ์šฐ root๋ฅผ ์”Œ์–ด์ค€ ๊ฐ’์ด ์•ฝ์ˆ˜๊ฐ€ ๋œ๋‹ค.(๋ฃจํŠธn๊นŒ์ง€ ํ™•์ธํ•ด์•ผํ•œ๋‹ค.) ์‹œ๊ฐ„๋ณต์žก๋„ 1๋ฒˆ ๋ฐฉ๋ฒ• : O(n) 2๋ฒˆ ๋ฐฉ๋ฒ• : O(√n) // 1๋ฒˆ ๋ฐฉ๋ฒ• O(n) int n = 121; for(int i = 1; i