간만에 봐도 잘 이해가안되는 문제가 생겨서 기록한다.. 그리고 기간이 얼마안남아서,, 흑흑 증말 어렵다
N개의 숫자들이 주어지면 주어진 숫자들을 전부 사용하여, 각 묶음으로 나눠 각각의 합을 구했을 때 첫 번째 묶음부터 순서대로 그 합이 짝수, 홀수, 짝수, 홀수, 짝수, … 이렇게 짝수에서 시작하여 짝홀이 계속 번갈아가면서 나오게끔 하는 만들 수 있는 최대 묶음 수를 구하는 프로그램을 작성해보세요. 단, 주어진 순서에 상관없이 묶음을 만들어도 됩니다.
입력 형식
첫 번째 줄에는 주어지는 숫자의 개수 N이 주어집니다.
두 번째 줄에는 N개의 숫자가 공백을 사이에 두고 주어집니다.
- 2 ≤ N ≤ 1,000
- 1 ≤ 주어지는 숫자들 ≤ 100
출력 형식
첫 번째 줄에 짝홀이 계속 번갈아가면서 나오게끔 하는 만들 수 있는 최대 묶음 수를 출력합니다.
입출력 예제
예제1
입력:
7
1 3 9 7 5 11 3
출력:
3
예제2
입력:
7
11 2 17 13 1 15 3
출력:
5
예제 설명
첫 번째 예제에서 1 3 9 7 5 11 3 이 주어졌습니다. 1 3 / 9 7 5 / 11 3 이렇게 묶음을 만들면 짝수, 홀수, 짝수가 되므로 조건을 만족하는 3개의 묶음을 만들 수 있게 됩니다. 1 3 / 9 / 7 5 / 11 이렇게 4개를 만들수도 있지만 원소 3이 하나 쓰이지 않고 남게 되기 때문에 이 방법은 사용할 수 없습니다.
Intuition
그룹의 숫자를 고를 때 어느 숫자를 고르던 그 숫자의 홀짝이 같다면 그룹의 총합에서 홀짝도 같아지게 됩니다. 따라서 어느 숫자를 골랐는지 알 필요가 없으며, 짝수와 홀수 중 어느 숫자를 새로 골랐는지만 정보를 가지고 있다면 문제를 풀 수 있습니다. 또한, 그룹을 나눌때는 숫자를 가능한 적게 사용해야 남은 숫자들로 더 많은 그룹을 만들 가능성이 생깁니다.
Algorithm
묶음이 짝수, 홀수 순서로 번갈아가며 나오게 해야 합니다.
-
짝수 묶음을 만들 때에는 짝수 숫자 1개로 그룹을 만드는 것이 최선이며, 만약 짝수 숫자가 부족하다면, 홀수 숫자 2개로 그룹을 만드는 것이 최선입니다.
-
홀수 묶음을 만들 때에는, 홀수 숫자 1개로 그룹을 만드는 것이 최선이며, 짝수 숫자만으로는 홀수 묶음을 만들 수 없습니다.
홀수만 존재하는 예제를 알아봅시다. 다음과 같은 7개의 홀수가 주어져있습니다.
예제에서는 홀수밖에 주어지지 않았으므로, odd의 값이 7이 되고 짝수그룹, 홀수그룹 순서로 묶습니다.
이렇게 묶다보면 마지막에 홀수 3이 남습니다. 다음과 같이 이 3을 묶기 위해 11과 같이 묶어보았지만, 짝수그룹 2개가 연속되어 있으므로 불가능한 상태가 됩니다.
이 상태를 해결하기 위해 짝수그룹 (7, 5)와 짝수그룹 (11, 3)를 하나로 묶어 해결합니다.
이렇게 총 3개의 그룹으로 묶어 해결할 수 있습니다.
이번엔 홀수와 짝수가 같이 존재하는 예제를 알아봅시다. 다음과 같은 6개의 짝수 또는 홀수가 주어져있습니다.
이번에는 짝수 4가 있으므로, 맨 처음에 짝수그룹에 4만 넣습니다.
그 후, 짝수와 홀수 순서대로 묶다보면 마지막에 홀수 3이 남습니다. 3을 묶기 위해 7과 같이 묶어보았지만, 짝수그룹 2개가 연속되어 있으므로 불가능한 상태가 됩니다.
이 상태를 해결하기 위해 짝수그룹 (9, 7)와 짝수그룹 (5, 3)를 하나로 묶어 해결합니다.
이렇게 총 3개의 그룹으로 묶어 해결할 수 있습니다.
코드
import java.util.Scanner;
public class Main {
public static final int MAX_N = 1000;
public static int n;
public static int[] blocks = new int[MAX_N];
public static int odd, even;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력:
n = sc.nextInt();
for(int i = 0; i < n; i++)
blocks[i] = sc.nextInt();
// 생각해 보면, 그룹의 숫자를 고를 때 어느 숫자를 고르던
// 그 숫자의 홀짝이 같다면 그룹의 총합에서 홀짝도 같아지게 됩니다.
// 따라서 어느 숫자를 골랐는지 알 필요가 없으며, 짝수와 홀수 중 어느 숫자를
// 새로 골랐는지만 정보를 가지고 있다면 문제를 풀 수 있습니다.
for(int i = 0; i < n; i++) {
if(blocks[i] % 2 == 0)
even++;
else
odd++;
}
// 그룹을 나눌때 숫자를 가능한 적게 쓰는 것이 유리합니다. 숫자를 적게 사용해야
// 남은 숫자들로 더 많은 그룹을 만들 가능성이 생기기 때문입니다.
// 생각해보면, 홀수 그룹을 만들 때 짝수 숫자를 그룹에 넣는것은 의미가 없습니다.
// 짝수 숫자를 넣으나 마나 어차피 그룹의 홀짝성이 변하지 않기 때문입니다.
// 따라서 홀수 그룹을 만들 때에는 짝수 숫자를 넣지 않고 홀수 숫자만 1개로
// 그룹을 형성하는 것이 유리합니다.
// 짝수 그룹을 만들 때에는 홀수 2개로 만들거나 짝수 1개로 만들 수 있는데,
// 홀수 그룹을 만들 때에 사용되지 않는 짝수 숫자부터 그룹에 이용하는 것이 유리합니다.
int groupNum = 0;
while(true) {
// 묶음을 짝수, 홀수를 번갈아가며 나오게끔 해야 하므로
// groupNum이 짝수일 때, 묶음은 짝수로 만들어야 하고
// groupNum이 홀수일 때, 묶음은 홀수로 만들어야 합니다.
if(groupNum % 2 == 0) {
// 짝수 묶음을 만들 때에는, 짝수 숫자 1개로 그룹을 만드는 것이 최선입니다.
// 만약 짝수 숫자가 부족하다면, 홀수 숫자 2개로 그룹을 만드는 것이 최선입니다.
if(even > 0) {
even--;
groupNum++;
}
else if(odd >= 2) {
odd -= 2;
groupNum++;
}
else {
// 더 이상 그룹을 만들지 못하는 상황입니다.
// 아직 숫자가 남아있다면 남아 있는 숫자들로 짝수 그룹을 만들지 못합니다.
// 이 경우 ... + (짝수 그룹 A) + (홀수 그룹 B) + (나머지 C(홀수 그룹))
// 다음과 같은 상태인데, 무슨 짓을 해도 그룹의 개수를 늘리거나 유지해서는
// 문제 조건을 만족할 수 없습니다.
// 그 이유는 그룹의 개수를 늘리려면 ... + 짝수 그룹 + 홀수 그룹 + 짝수 그룹 형태가,
// 그룹의 개수를 유지하려면 ... + 짝수 그룹 + 홀수 그룹 형태가 되어야만 하는데
// 홀짝성을 생각해 보았을 때 이는 불가능합니다.
// 따라서 그룹의 개수를 1개 줄이는
// ... + 짝수 그룹(A + B + C) 형태가 최선입니다.
if(even > 0 || odd > 0)
groupNum--;
break;
}
}
else {
// 홀수 묶음을 만들 때에는, 홀수 숫자 1개로 그룹을 만드는 것이 최선입니다.
// 짝수 숫자만으로는 홀수 묶음을 만들 수 없습니다.
if(odd > 0) {
odd--;
groupNum++;
}
else {
// 더 이상 그룹을 만들지 못하는 상황입니다.
// 아직 숫자가 남아있다면 남아 있는 숫자들로 홀수 그룹을 만들지 못합니다.
// 이 경우 ... + (홀수 그룹 A) + (짝수 그룹 B) + (나머지 C(짝수 그룹))
// 다음과 같은 상태인데, 무슨 짓을 해도 그룹의 개수를 늘리는 방식으로는
// 문제 조건을 만족할 수 없습니다.
// 그 이유는 그룹의 개수를 늘리려면 ... + 홀수 그룹 + 짝수 그룹 + 홀수 그룹 형태가
// 되어야만 하는데 홀짝성을 생각해 보았을 때 이는 불가능합니다.
// 따라서 그룹의 개수를 유지하는
// ... + (홀수 그룹 A) + (짝수 그룹 (B + C)) 형태가 최선입니다.
break;
}
}
}
System.out.print(groupNum);
}
}
'코딩테스트 > 문제풀이' 카테고리의 다른 글
[Softeer] [21년 재직자 대회 예선] 전광판 (0) | 2024.05.22 |
---|---|
[코드트리] 수열의 순서 바꾸기 (1) | 2023.05.15 |
[코드트리] 세 수의 최대 곱 (0) | 2023.05.14 |
[코드트리] ABC 줄 세우기 (1) | 2023.05.12 |
[코드트리] X 달리기 (0) | 2023.05.09 |