DP

    [BOJ_2156] ํฌ๋„์ฃผ ์‹œ์‹ (java)

    [BOJ_2156] ํฌ๋„์ฃผ ์‹œ์‹ (java)

    ๋ฌธ์ œ๋งํฌ https://www.acmicpc.net/problem/2156 2156๋ฒˆ: ํฌ๋„์ฃผ ์‹œ์‹ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ www.acmicpc.net ๋ฌธ์ œ์„ค๋ช… ๋”๋ณด๊ธฐ ๋”๋ณด๊ธฐ ๋ฌธ์ œ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ์น™์ด ์žˆ๋‹ค. ํฌ๋„์ฃผ ์ž”์„ ์„ ํƒํ•˜๋ฉด ๊ทธ ์ž”์— ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ๋Š” ๋ชจ๋‘ ๋งˆ์…”์•ผ ํ•˜๊ณ , ๋งˆ์‹  ํ›„์—๋Š” ์›๋ž˜ ์œ„์น˜์— ๋‹ค์‹œ ๋†“์•„์•ผ ํ•œ๋‹ค. ์—ฐ์†์œผ๋กœ ๋†“์—ฌ ์žˆ๋Š” 3์ž”์„ ๋ชจ๋‘ ๋งˆ์‹ค ์ˆ˜๋Š” ์—†๋‹ค...

    [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๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , ..