코딩테스트 : 2629번 양팔저울
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 27852 9722 7036 34.946%
문제
양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.
무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.
구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.
<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.
추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.
<그림 2> 구슬이 5g인지 확인하는 방법
입력
첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.
출력
주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.
public class BackJoon
{
public static void Main()
{
// 총 숫자 갯수
int N = int.Parse(Console.ReadLine());
int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
// 찾아야 하는 무게
int K = int.Parse(Console.ReadLine());
int[] weight = Console.ReadLine().Split().Select(int.Parse).ToArray();
// idea : 더해서 가능한 모든 무게들을 저장, 동시에 남아 있는 모든 숫자들을 차례대로 빼 본다.
// 추가 30개니까 가능하겠지만 과연 효율적인 방법일까 ?
//idea2 : 추는 결국 한 번씩만 사용가능하다, 그러니까 추를 순서대로 순회하면서 +/-를 통해 가능한 무게를 모두 찾는다.
int[] DP = new int[numbers.Sum() + 1];
DP[0] = 1;
for (int i = 0; i < numbers.Count(); i++)
{
int currentWeight = numbers[i];
for (int j = 0; j < DP.Length - currentWeight; j++)
{
// 그 무게가 가능한 무게라면
if (DP[j] == 1)
{
// 아무것도 더해지지 않는 것이 1이면 , 이미 가능하므로 더해주지 않는다.
// 순서대로 무게를 사용함으로 중복이 방지된다.
DP[j + currentWeight] = 1;
if ( j > currentWeight ) DP[j - currentWeight] = 1;
}
}
}
for (int i = 0; i < weight.Count(); i++)
{
if ( DP[weight[i]] == 1) Console.Write("Y ");
else Console.Write("N ");
}
}
}
아이디어 2 를 채택했다, 조금 더 보충설명하자면 다음과 같다.
아이디어 2: 각 추는 한 번씩만 사용할 수 있으므로, 모든 추를 순차적으로 하나씩 선택해가며 가능한 무게를 더하거나 빼는 방식으로 탐색한다. 이 과정을 통해 만들 수 있는 모든 무게 조합을 구할 수 있다.
1. 두 가지 이상의 값을 갱신할 때는 값을 복사해서 놔 둔 뒤에 해야 함, 안그럼 전의 값이 영향을 미침
예를 들어 같은 반복에서 1을 두 번 더하거나, 뺀 값이 DP에 저장되고, 그 값을 다시 사용하게 됨.
2. 순서대로 1 ,3 , 5 의 추가 있다면 2를 만들 수 있으나, 위의 식에서는 만들 수 없음, 배열의 인덱스가 0보다 작아지면 아예 계산을 하지 않기 때문, 이를 처음에는 음수 배열 ( 전체적으로 2배를 한 후 , 절반의 값을 더해주는 방식 ) 으로 해결하려 했으나 절대값으로 해결
3. 무게추의 추가, 전체 값을 더한 것보다 큰 경우를 고려하지 않았음.
public class BackJoon
{
public static void Main()
{
// 총 숫자 갯수
int N = int.Parse(Console.ReadLine());
int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
// 찾아야 하는 무게
int K = int.Parse(Console.ReadLine());
int[] weight = Console.ReadLine().Split().Select(int.Parse).ToArray();
// idea : 더해서 가능한 모든 무게들을 저장, 동시에 남아 있는 모든 숫자들을 차례대로 빼 본다.
// 추가 30개니까 가능하겠지만 과연 효율적인 방법일까 ?
//idea2 : 추는 결국 한 번씩만 사용가능하다, 그러니까 추를 순서대로 순회하면서 +/-를 통해 가능한 무게를 모두 찾는다.
int[] DP = new int[numbers.Sum() + 1];
DP[0] = 1;
for (int i = 0; i < numbers.Count(); i++)
{
int currentWeight = numbers[i];
int[] nextDP = new int[DP.Length];
Array.Copy(DP, nextDP, DP.Length);
for (int j = 0; j < DP.Length - currentWeight; j++)
{
// 그 무게가 가능한 무게라면
if (DP[j] == 1)
{
// 아무것도 더해지지 않는 것이 1이면 , 이미 가능하므로 더해주지 않는다.
// 순서대로 무게를 사용함으로 중복이 방지된다.
nextDP[j + currentWeight] = 1;
nextDP[Math.Abs(j - currentWeight)] = 1;
}
}
DP = nextDP;
}
for (int i = 0; i < weight.Count(); i++)
{
if (weight[i] < DP.Length && DP[weight[i]] == 1) Console.Write("Y ");
else Console.Write("N ");
}
}
}
bool로 했으면 더 편했을 것 같고, 다른 방식으로도 풀 수 있을 듯 하다.