๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] 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);
}
}