백준 : 2961번, 도영이가 만든 맛 있는 음식

문제 주소 : www.acmicpc.net/problem/2961

정답 비율 : 40.917% (2021.02.17 21:31 기준)

2961번: 도영이가 만든 맛있는 음식

문제 요약 :

N개의 (x, y) 좌표가 주어집니다. 1 ~ N개의 좌표를 선택하여 x좌표끼리는 곱하고 y좌표끼리는 합한 값의 차이가 가장 작은 값을 출력합니다.

EX)

4

1 7

2 6

3 8

4 9

답 : 1

(2, 6) , (3, 7) , (4, 8)을 선택할 때 2x3x4=24, 6+7+8=25으로 차이가 1이 됩니다.

 

문제 조건 :

입력 : N 값이 주어지고 이어서 N개의 좌표를 주어집니다. N의 범위는 1 ~ 10입니다. 모든 좌표를 선택했을 때 x좌표 곱의 결과와 y좌표 합의 결과는 1,000,000,000 보다 작습니다.

출력 : x좌표 곱의 결과와 y좌표 합의 결과 차이가 가장 작은 값을 출력합니다.

시간 : 1 초

 

문제 풀이 :

해당 문제는 조합 문제입니다. 이때 N의 최대 값이 10이므로 최대 모든 경우의 수는 2^10 - 1 = 1023으로 큰 수가 아닙니다. 모든 경우를 검증하면 됩니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int arr[2][10]; //0 : S, 1 : B
int ans =  1000000001;

void dfs(int depth, int max, int S, int B)
{
	if(depth == max)
	{
		if (S != 1 && B != 0)
			ans = ans < (S > B ? S - B : B - S) ? ans : ( S > B ? S - B : B - S);
	}
	else
	{
		int i = -1;
		
		for(i = 0; i < 2; i++)
		{
			if(i)
				dfs(depth + 1, max, S * arr[0][depth], B + arr[1][depth]);
			else
				dfs(depth + 1, max, S, B);
		}
	}
}

int main()
{
	int N, i = -1;
	scanf("%d", &N);
	
	for(i = 0; i < N; i++)
		scanf("%d %d", &arr[0][i], &arr[1][i]);
	dfs(0, N, 1, 0);
	
	printf("%d\n", ans);
	return 0;
}

 

-> ans < (S > B ? S - B : B - S) ? ans : ( S > B ? S - B : B - S) 이 것의 의미는 ans가 |S - B| 보다 작으면 ans를 유지하고 클 경우 |S-B|로 바꿉니다.

 

Python3

#solve 2961
import sys  
sys.setrecursionlimit(10**8)

ans = 1000000001
n = int(input())
location = []

def dfs(depth, M, S, B):
    if depth == M :
        if S!=1 and B!=0:
            global ans
            ans = min(ans, abs(S - B))
    else:
        for i in range(2):
            if i:
                dfs(depth+1, M, S*location[depth][0], B+location[depth][1])
            else:
                dfs(depth+1, M, S, B)

for i in range(n):
    tmp = list(map(int,input().split()))
    location.append(tmp)
dfs(0, n, 1, 0)
print(ans)

 

-> 문제를 해결하였지만 너무 C언어스러운 코드이어서 다르게 작성하려고 시도하였습니다.

 

아이디어 : 모든 경우의 수를 배열에 저장하면 DFS가 아니라 한 줄의 for으로 문제를 해결할 수 있을 거 같다고 생각하였습니다.

 

코드는 다음과 같습니다.

 

Python3

#solve 2961

n = int(input())
ans = [[1, 0]]
result = []

for i in range(n):
    x, y = list(map(int,input().split()))
    ans += [[a*x, b+y] for a, b in ans]

ans.pop(0)    
while ans:
    x, y = ans.pop(0)    
    result.append(abs(x-y))
    
print(min(result))

 

 

-> 이렇게 되면 새로운 좌표가 들어오면 기존 만들어진 좌표에 추가하여 입력이 종료될 때 result에는 모든 경우에 대한 좌표 값들을 가지게 됩니다.

 

***

다른 사람의 코드를 확인하니 min(abs(x-y) for x, y in ans[1:]) 이런 방식으로 min함수 내부에 컴프리헨션을 사용하는 것을 확인하였습니다. 좋은 정보를 얻었습니다. ㅎㅎ