[BOJ/백준] 14568번 : 2017 연세대학교 프로그래밍 경시대회 (Java)

14568번 : 2017 연세대학교 프로그래밍 경시대회 (https://www.acmicpc.net/problem/14568)

---

문제

---

접근 방법

---

• 영훈과 남규의 사탕 수는 서로 영향을 주기 때문에 택희가 가지는 사탕 수를 먼저 제외하고, 제외한 값에 대해 남규와 영훈에게 나누어 줄 수 있는 경우의 수를 계산한다.

• 택희가 가질 수 있는 사탕의 수

  • 사탕의 수가 홀수개가 될 수 없기 때문에 2씩 증가
  • 최솟값은 2
  • 영훈과 남규의 합의 최솟값이 4이므로 최댓값은 N-4

• 영훈이 가질 수 있는 사탕의 수

  • 최솟값은 1
  • 남규보다 2개 이상으로 적은 사탕을 가져야 하므로 최댓값은 ((택희의 사탕 수를 제외한 개수) / 2(소수점 버림) - 1)

• 따라서 택희가 가지는 사탕 수를 2부터 N-4까지 2씩 증가한 값으로 정하고, 정해진 택희의 사탕 수에 대해 남규가 가질 수 있는 개수의 경우의 수(최댓값 - 최솟값)의 합을 출력한다.

코드

---

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int sum = 0;
		for (int i = 2; i <= N - 4; i += 2) {
			int yn = N - i;
			sum += yn / 2 - 1;
		}
		bw.write(String.valueOf(sum));
		bw.flush();
		bw.close();
		br.close();
	}
}

위의 코드의 성능

정리

---

각자 가질 수 있는 값의 최댓값, 최솟값을 알고, 영훈의 값은 남규의 값에 의해 정해지기 때문에 택희가 가질 수 있는 사탕의 수에 대해 남규가 가질 수 있는 사탕의 경우의 수의 합을 구하는 것이 포인트이다.