๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.2163 ์ดˆ์ฝœ๋ฆฟ ๋‚˜๋ˆ„๊ธฐ

๐Ÿ“– ๋ฌธ์ œ

https://www.acmicpc.net/problem/2163

์ •ํ™”๋Š” Nร—M ํฌ๊ธฐ์˜ ์ดˆ์ฝœ๋ฆฟ์„ ํ•˜๋‚˜ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ดˆ์ฝœ๋ฆฟ์€ ๊ธˆ์ด ๊ฐ€ ์žˆ๋Š” ๋ชจ์–‘์„ ํ•˜๊ณ  ์žˆ์œผ๋ฉฐ, ๊ทธ ๊ธˆ์— ์˜ํ•ด Nร—M๊ฐœ์˜ ์กฐ๊ฐ์œผ๋กœ ๋‚˜๋ˆ ์งˆ ์ˆ˜ ์žˆ๋‹ค.

์ดˆ์ฝœ๋ฆฟ์˜ ํฌ๊ธฐ๊ฐ€ ๋„ˆ๋ฌด ํฌ๋‹ค๊ณ  ์ƒ๊ฐํ•œ ๊ทธ๋…€๋Š” ์ดˆ์ฝœ๋ฆฟ์„ ์นœ๊ตฌ๋“ค๊ณผ ๋‚˜๋ˆ  ๋จน๊ธฐ๋กœ ํ–ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด์„œ ์ •ํ™”๋Š” ์ดˆ์ฝœ๋ฆฟ์„ ๊ณ„์† ์ชผ๊ฐœ์„œ ์ด Nร—M๊ฐœ์˜ ์กฐ๊ฐ์œผ๋กœ ์ชผ๊ฐœ๋ ค๊ณ  ํ•œ๋‹ค. ์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐค ๋•Œ์—๋Š” ์ดˆ์ฝœ๋ฆฟ ์กฐ๊ฐ์„ ํ•˜๋‚˜ ๋“ค๊ณ , ์ ๋‹นํ•œ ์œ„์น˜์—์„œ ์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐ ๋‹ค. ์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐค ๋•Œ์—๋Š” ๊ธˆ์ด ๊ฐ€ ์žˆ๋Š” ์œ„์น˜์—์„œ๋งŒ ์ชผ๊ฐค ์ˆ˜ ์žˆ๋‹ค. ์ด์™€ ๊ฐ™์ด ์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐœ๋ฉด ์ดˆ์ฝœ๋ฆฟ์€ ๋‘ ๊ฐœ์˜ ์กฐ๊ฐ์œผ๋กœ ๋‚˜๋ˆ ์ง€๊ฒŒ ๋œ๋‹ค. ์ด์ œ ๋‹ค์‹œ ์ด ์ค‘์—์„œ ์ดˆ์ฝœ๋ฆฟ ์กฐ๊ฐ์„ ํ•˜๋‚˜ ๋“ค๊ณ , ์ชผ๊ฐœ๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋ฉด ๋œ๋‹ค.

์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐœ๋‹ค๋ณด๋ฉด ์ดˆ์ฝœ๋ฆฟ์ด ๋…น์„ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, ์ •ํ™”๋Š” ๊ฐ€๊ธ‰์ ์ด๋ฉด ์ดˆ์ฝœ๋ฆฟ์„ ์ชผ๊ฐœ๋Š” ํšŸ์ˆ˜๋ฅผ ์ตœ์†Œ๋กœ ํ•˜๋ ค ํ•œ๋‹ค. ์ดˆ์ฝœ๋ฆฟ์˜ ํฌ๊ธฐ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ 1ร—1 ํฌ๊ธฐ์˜ ์ดˆ์ฝœ๋ฆฟ์œผ๋กœ ์ชผ๊ฐœ๊ธฐ ์œ„ํ•œ ์ตœ์†Œ ์ชผ๊ฐœ๊ธฐ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

n * m ์ดˆ์ฝœ๋ฆฟ์„ 1 * 1 ๋กœ ๋งŒ๋“ค์–ด์•ผํ•ฉ๋‹ˆ๋‹ค.
1 * m ์œผ๋กœ ๋งŒ๋“œ๋ ค๋ฉด n-1 ๋ฒˆ ๋‚˜๋ˆ ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์ด๋ ‡๊ฒŒ ๋˜๋ฉด n ๊ฐœ์˜ 1 * m ์ดˆ์ฝœ๋ฆฟ์ด ์ƒ๊น๋‹ˆ๋‹ค.
1 * m ์ดˆ์ฝœ๋ฆฟ์„ 1 * 1 ์ดˆ์ฝœ๋ฆฟ์œผ๋กœ ๋งŒ๋“œ๋ ค๋ฉด m - 1 ๋ฒˆ ๋‚˜๋ˆ„๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๊ฒฐ๊ณผ์ ์œผ๋กœ

์ชผ๊ฐœ๊ธฐํšŸ์ˆ˜ = (n - 1) + n * (m - 1)

์ž…๋‹ˆ๋‹ค. 

๐Ÿ’ป ์ฝ”๋“œ

package problem.dynamic.Q2163;

import java.io.*;

public class Main_2163 {
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(Integer.toString(solve()));
        bw.flush();
        bw.close();
    }
    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        br.close();
    }
    public static int solve(){
        return (n-1) + n*(m-1);
    }

}


Written on April 30, 2020