읍내리 까치골
[C++] 백준 33665: 트레이드 AI - 단순 구현 본문
solved.ac 프로필배경이 어떤게 추가가 되었나 둘러보다가, 옛날같았으면 대회에 참여해야 주던 배경을 이제는 문제 풀이로도 받을 수 있는 것들이 생겼다는 것을 보게 되었습니다. 기왕 봤는데... 해봐야겠죠?
(결론부터 말하자면 일단 얻었습니다)
33665번 문제는 단순 구현 문제이며 링크는 아래와 같습니다.
https://www.acmicpc.net/problem/33665
문제 파악
입력 형태가 조금 복잡해 보이고 모노폴리라는 게임을 언급하여 문제 풀이가 어려워 보일 수도 있는데, 이해하고 나면 크게 어려운 것 없이 진행하실 수 있을 것이라 생각합니다. 핵심 문장은 아래입니다.
게임을 하는 도중에 트레이드 조건이 주어질 때, 트레이드가 자신에게 이득인지를 파악하는 것이 이 문제의 핵심입니다. 현상 유지 또는 자산의 증가라면 YES, 자산의 감소를 불러올 경우 NO를 출력하는 것입니다.
입력 형식 분석
입력 형식과 함께 문제의 주요 변수를 살펴보겠습니다.
일단 게임 내 40개의 도시가 존재하며, 이 문제는 보유한 도시의 트레이딩에서 이익을 찾는 것입니다. 총 10개의 구역이 존재하고, 각 구역별로 4개의 도시가 존재합니다. 구역 내 도시의 각 가격은 동일한 것으로 간주하되, 구역 내 몇 개의 도시를 보유하느냐에 따라 자산 가치가 달라지는 것으로 생각하면 되겠습니다. 이 때 자산 가치는 선형이 아님에 유의합니다. (서초구에 부동산 4개를 소유하면 떼부자가 될 수도 있겠지만 다주택자로 과세폭탄을 맞을 수 있음을 생각하면 될 것 같습니다)
11번째 줄은 도시의 소유자를 의미, 0은 소유주 없음, 1은 나의 도시, 2는 상대의 도시입니다.
12번째 줄은 트레이딩 희망이며 1의 경우 내가 상대로부터 도시를 매입하고자 할 때, 2의 경우 상대가 내 도시를 매입하고자 함을 의미합니다.
13번째 줄은 담보의 유무를 의미하는데, 도시에 담보가 잡혔을 경우 자산 가치를 낮게 간주합니다. 감산은 비율이 아닌 정액제로 가장 마지막 줄(19번째 줄)입니다.
14번째 줄은 내가 가지고 있는 현금, 15번째 줄은 상대가 가지고 있는 현금이며, 16번째 줄은 내가 상대의 도시를 매입하기 위해 제시한 현금(2000원을 줘야 함)이고 17번째 줄은 상대가 나의 도시를 매입하기 위해 제시한 현금(4000원을 받게 됨)입니다.
마지막으로 18번째 줄은 현금 가치의 비율을 얼마로 볼 것인지에 대한 백분율 값이며 예제 3번 입력의 경우 10이므로 10%입니다. (만 원 소유 시 천 원으로 봄)
필요 변수
각 구역마다 도시를 0개부터 4개까지 5단계로 보유 상태를 가질 수 있고, 그에 따라 자산 가중치가 달라집니다. 또한 도시의 담보 여부에 따라 자산의 평가액 감소가 이뤄집니다. 트레이딩의 수락/거부 의사 결정을 위하여 트레이딩 전과 후의 가치를 각각 계산하여야 합니다. 따라서 아래의 변수가 필요할 것으로 판단하였습니다.
- 각 구역 별 보유 도시 개수에 따른 평가액 : int value[][]
- 현재 보유 중인 도시 현황 : int owner[][]
- 트레이드 후 보유 예정인 도시 : int trade[][]
- 도시의 담보 여부 : int mortgage[][]
- 현재 가지고 있는 현금 : int cash
- 제시한 거래액 : int price
- 거래 이후 가지고 있을 잔액 : int change
- 자산 총계 : int sum
위 내용을 코드로 작성하여 아래와 같이 정리하였습니다.
// ============================== Declare Variables ===============================
int value[10][5] = {0}; // 1 ~ 10
int owner[10][6] = {0}; // 11
int trade[10][6] = {0}; // 12
bool mortgage[10][5] = {false}; // 13
string tmp; // for 11~13
int cashA, cashB, priceA, priceB, cashRate, mortgagePrice, // 14~19
resultBefore = 0, resultAfter = 0, changeA, changeB,
beforeSumA = 0, afterSumA = 0, beforeSumB = 0, afterSumB = 0,
beforeMortgageA = 0, afterMortgageA = 0, beforeMortgageB = 0, afterMortgageB = 0;
자산 총계 계산 시 담보액을 따로 계산하기 위하여 별도의 변수로 작성하였으며, 거래 전/후 비교가 필요하므로 before/after로 구분하였습니다. 변수명에서 A는 나, B는 상대를 의미합니다.
owner와 trade 2차원 배열은 열을 총 6개로 설정하였는데, 각 구역의 1,2,3,4번 도시의 소유 여부를 확인하기 위해 1~4번 열을 소유자(1, 2)를 표시하는데 사용하였습니다. 이 문제에서는 구역 내 도시를 "몇 개" 소유하였느냐가 핵심입니다. (구역 내 어느 도시를 소유하였는지는 중요하지 않습니다 - 담보 확인 시에만 사용.) 따라서 0번 열을 구역 내 내가 소유한 도시의 개수, 5번 열을 상대가 소유한 도시의 개수로 사용하였습니다. 담보(mortgage)의 0번 열은 버리는 열이 되었습니다. 계산의 정확성 및 분석 용이를 위해 1~4번으로 통일하였습니다.
입력 받기
이제 앞서 분석한 내용에 맞추어 입력을 받을 차례입니다. 계산 과정은 입력 이후에 설명하도록 하겠습니다. 데이터의 순서대로 입력 과정을 나누어 설명하였습니다.
- 각 구역의 보유 도시 수에 따른 자산 가중치
// ================================ Input Values ===================================
// line 1 ~ 10 - values of city
for (int i=0; i<10; i++)
cin >> value[i][1] >> value[i][2] >> value[i][3] >> value[i][4];0번 구역부터 10번 구역까지, 자산 가중치를 입력합니다. 0개 보유시에는 자산 가치가 0이므로 별도 설정하지 않습니다.
- 각 도시의 소유자 상태
// line 11 Owner
cin>>tmp;
for (int i=0; i<40; i++) {
owner[i/4][i%4+1] = tmp[i]-'0';
}owner 배열을 2차원으로 설정하였는데 입력은 0, 1, 2로 구성된 40개의 숫자로 들어옵니다. 따라서 string으로 받은 뒤 각 자리를 돌며 값을 할당합니다. 4개씩 끊어야 하므로 i/4, i%4 연산을 통해 2차원으로 변환시켜 주었습니다. (integer 연산에 따라 나눗셈 연산 시 소수점은 절사됩니다.) 모듈러 연산은 4일 경우 0, 1, 2, 3이 나오므로 +1 해주었습니다.
- 트레이딩 후 소유자 상태
// line 12 Trade
cin>>tmp;
for (int i=0; i<40; i++) {
if (tmp[i] == '0')
trade[i/4][i%4+1] = owner[i/4][i%4+1];
else
trade[i/4][i%4+1] = tmp[i]-'0';
}트레이딩을 진행하게 될 경우 기존의 소유 상태에서 교환을 희망하는 도시만 변경이 이루어집니다. 도시의 트레이딩은 상대가 소유한 도시를 희망하는 것이기 때문에, 기존 상태에서 소유권이 없던 도시(0)는 그대로 두면 됩니다. 또한 트레이딩 대상이 아닌 도시도 그대로 두면 되고, 트레이딩 희망하는 경우만 반영하면 되겠습니다.
따라서 트레이딩 희망 여부가 0인 경우 기존의 값 복사, 그 외의 값인 경우 신규 소유자로 덮어씌우면 되겠습니다.
- 담보 여부
// line 13 Mortgage
cin>>tmp;
for (int i=0; i<40; i++) {
mortgage[i/4][i%4+1] = tmp[i]-'0';
}담보 여부를 저장하는 mortgage는 boolean 배열로 0(false)과 1(true)를 저장 가능합니다. 주어지는 입력도 0과 1이므로 해당 형식에 맞게 저장해줍니다. 이 배열은 자산 계산 시 도시 소유자 정보와 연동하면 됩니다.
- 보유 현금, 제시 가격, 현금 평가비율, 담보 페널티 금액, 거래 후 보유 현금
// 나머지 라인
// line 14 ~ 15 Cash
cin>>cashA>>cashB;
// line 16 ~ 17 Price
cin>>priceA>>priceB;
// line 18 ~ 19 Rate
cin>>cashRate>>mortgagePrice;
// Cash at after trade
changeA = cashA - priceA + priceB, changeB = cashB - priceB + priceA;나머지 입력 부분입니다. 그대로 정수 변수들에 모두 저장해주면 되겠습니다. 입력이 끝난 후 거래 후 보유 현금을 미리 계산해두었습니다. A의 잔고는 최초 A의 현금 보유액에서 B에게 준 금액(priceA)을 제하고 B에게 받은 금액(priceB)을 더해주면 됩니다. B의 잔고도 동일하게 처리하면 됩니다.
이로써 입력 과정이 끝났습니다.
자산 계산하기
입력을 받아왔으니 이제 계산만 하면 됩니다.
거래 전 후로 A(나)와 B(상대)의 도시 보유 상태와 담보 여부 및 현금 계산만 해주면 됩니다. 도시가 40개씩이나 되어서 복잡해보일 수도 있는데 속성이 도시, 담보, 현금 3가지이기에 간단하게 계산이 가능합니다. 변수가 많아서 조금 헷갈릴 수는 있습니다.
- 거래 전/후 보유 도시 개수 계산
// ============================== Calculate Result =================================
// sum of city
for (int i=0; i<10; i++) {
// loop in 10 color
for (int j=1; j<=4; j++) {
// loop in 4 city in each color
if (owner[i][j] == 1) owner[i][0]++;
if (owner[i][j] == 2) owner[i][5]++;
if (trade[i][j] == 1) trade[i][0]++;
if (trade[i][j] == 2) trade[i][5]++;
}
}앞서 owner 배열과 trade 배열의 각각 0열과 5열을 A와 B의 보유 도시 개수를 저장하기 위해 6열짜리로 선언했다고 언급했었습니다. 그에 맞게 각 구역 별 A와 B의 보유 도시 개수를 계산해줍니다. owner 배열이 거래 이전 원래 소유자, trade 배열이 거래 이후 변경된 소유 상태를 저장한 배열입니다.각 배열 0열과 5열은 0부터 3사이의 값을 갖게 됩니다.
- 거래 전 자산에 대한 계산
// Before Trade----------------------------
// City value
for (int i=0; i<10; i++) {
beforeSumA += value[i][owner[i][0]];
beforeSumB += value[i][owner[i][5]];
}
// Cash value
beforeSumA += cashA * cashRate / 100;
beforeSumB += cashB * cashRate / 100;
// Mortgage
for (int i=0; i<10; i++)
for (int j=1; j<=4; j++)
if (mortgage[i][j] == true) {
if (owner[i][j] == 1) beforeMortgageA++;
if (owner[i][j] == 2) beforeMortgageB++;
}
beforeSumA -= mortgagePrice * beforeMortgageA;
beforeSumB -= mortgagePrice * beforeMortgageB;
// result
resultBefore = beforeSumA - beforeSumB;자산에 대한 계산은 도시의 보유 가치 + 현금 가치 - 담보 페널티 금액입니다. 10개 구역 각각의 보유 도시 개수에 따른 자산 가치를 합하고, 그 다음 현금 보유액에 평가 비율을 곱하여 합하고, 보유 도시에서 담보에 해당하는 개수만큼 페널티 금액을 곱해 제합니다. 이 과정을 거쳐 A와 B의 합계(Sum)를 도출하고 거래 전 계산 값으로 저장합니다.
- 거래 후 자산에 대한 계산
// After Trade-----------------------------
// City value
for (int i=0; i<10; i++) {
afterSumA += value[i][trade[i][0]];
afterSumB += value[i][trade[i][5]];
}
// Cash value
afterSumA += changeA * cashRate / 100;
afterSumB += changeB * cashRate / 100;
// Mortgage
for (int i=0; i<10; i++)
for (int j=1; j<=4; j++)
if (mortgage[i][j] == true) {
if (trade[i][j] == 1) afterMortgageA++;
if (trade[i][j] == 2) afterMortgageB++;
}
afterSumA -= mortgagePrice * afterMortgageA;
afterSumB -= mortgagePrice * afterMortgageB;
resultAfter = afterSumA - afterSumB;거래 후 자산 계산도 동일한 과정을 거치게 됩니다. 변수명만 차이가 있고 나머지는 동일한 과정을 거칩니다.
정답 도출
전/후 자산 평가액을 모두 구하였으므로 두 값을 비교하여 결과값을 출력하면 됩니다.
// ================================ Print Answer ===================================
if (resultAfter - resultBefore >= 0)
cout << "YES";
else
cout << "NO";
return 0;트레이딩 후의 자산 차이 값이 트레이딩 전보다 크거나 같으면 YES입니다. 자산 차이가 줄어들었다는 것은 격차가 좁혀졌다는 뜻이고, 내가 손해를 보았다는 뜻이니 트레이딩을 거절하여야(NO)합니다. 자산 차이 값이 음수 (내가 상대한테 지고 있던 경우) 또한 동일한 결과를 갖습니다.
번외: 차트 출력
백준 문제 페이지에서는 각 예제에 대하여 비교 차트를 제공하고 있습니다. 본 문제는 변수의 종류가 너무 많은 관계로 저도 풀이 중 디버그 목적으로 아래와 같은 차트 표시 함수를 제작하여 활용하였습니다.
void printChart() {
printf("\n\n");
printf(" | Before Trade | After Trade\n");
printf(" | Me | Rival | Me | Rival \n");
printf(" |Origin Convert|Origin Convert|Origin Convert|Origin Convert\n");
printf("--------------------------------------------------------------------------\n");
for (int i=0; i<10; i++)
printf(" City %c | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n", i+65,
owner[i][0], value[i][owner[i][0]], owner[i][5], value[i][owner[i][5]],
trade[i][0], value[i][trade[i][0]], trade[i][5], value[i][trade[i][5]]);
printf("--------------------------------------------------------------------------\n");
printf(" Cash | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n",
cashA, cashA*cashRate/100, cashB, cashB*cashRate/100,
changeA, changeA*cashRate/100, changeB, changeB*cashRate/100);
printf(" Mortgage | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n",
beforeMortgageA, beforeMortgageA*mortgagePrice, beforeMortgageB, beforeMortgageB*mortgagePrice,
afterMortgageA, afterMortgageA*mortgagePrice, afterMortgageB, afterMortgageB*mortgagePrice);
printf("--------------------------------------------------------------------------\n");
printf(" Sum | %6d | %6d | %6d | %6d\n",
beforeSumA, beforeSumB, afterSumA, afterSumB);
printf(" Distance | %6d | %6d\n", resultBefore, resultAfter);
}포맷 지정의 편의를 위하여 printf를 사용하였습니다. 입출력 속도를 위해 sync_with_stdio를 false로 설정하신 경우 printf 사용시 에러가 날 수 있습니다.
마무리
골드5 레벨의 문제 치고는 해법은 비교적 간단합니다. 문제의 태그도 '구현' 하나만 되어있습니다. 다만 변수의 종류가 워낙 많고, 변수 구성을 어떻게 하고 연산 처리를 어떻게 하느냐에 대하여 수 분 내 뚝딱 할만한 문제는 아닌 것 같아 해당 레벨이 붙은게 아닐까 싶습니다.
본 풀이는 마지막의 차트 출력 부분을 함께 보여주기 위해서 변수를 필요보다 많이 선언한 경향이 있습니다. 백준 PS 문제들의 경우 실무와는 다르게 원본 값의 보존이 중요하지 않은 경우가 많아 변수 재활용 등의 방법으로 풀이가 가능합니다. 풀이의 방법은 무궁무진하니 여러 방법 중 하나라고 생각해주시면 감사하겠습니다.
아래 전체 코드를 첨부하겠습니다. 그대로 갖다붙여 제출하시면 백준의 윤리 규정에 의거 시스템에 의해 계정에 제재를 받을 수 있으니 참고용으로만 보시기 바랍니다.
#include <iostream>
#define endl '\n'
using namespace std;
// ============================== Declare Variables ===============================
int value[10][5] = {0}; // 1 ~ 10
int owner[10][6] = {0}; // 11
int trade[10][6] = {0}; // 12
bool mortgage[10][5] = {false}; // 13
string tmp; // for 11~13
int cashA, cashB, priceA, priceB, cashRate, mortgagePrice, // 14~19
resultBefore = 0, resultAfter = 0, changeA, changeB,
beforeSumA = 0, afterSumA = 0, beforeSumB = 0, afterSumB = 0,
beforeMortgageA = 0, afterMortgageA = 0, beforeMortgageB = 0, afterMortgageB = 0;
void printChart();
int main() {
// ================================ Input Values ===================================
// line 1 ~ 10 - values of city
for (int i=0; i<10; i++)
cin >> value[i][1] >> value[i][2] >> value[i][3] >> value[i][4];
// line 11 Owner
cin>>tmp;
for (int i=0; i<40; i++) {
owner[i/4][i%4+1] = tmp[i]-'0';
}
// line 12 Trade
cin>>tmp;
for (int i=0; i<40; i++) {
if (tmp[i] == '0')
trade[i/4][i%4+1] = owner[i/4][i%4+1];
else
trade[i/4][i%4+1] = tmp[i]-'0';
}
// line 13 Mortgage
cin>>tmp;
for (int i=0; i<40; i++) {
mortgage[i/4][i%4+1] = tmp[i]-'0';
}
// line 14 ~ 15 Cash
cin>>cashA>>cashB;
// line 16 ~ 17 Price
cin>>priceA>>priceB;
// line 18 ~ 19 Rate
cin>>cashRate>>mortgagePrice;
// Cash at after trade
changeA = cashA - priceA + priceB, changeB = cashB - priceB + priceA;
// ============================== Calculate Result =================================
// sum of city
for (int i=0; i<10; i++) {
// loop in 10 color
for (int j=1; j<=4; j++) {
// loop in 4 city in each color
if (owner[i][j] == 1) owner[i][0]++;
if (owner[i][j] == 2) owner[i][5]++;
if (trade[i][j] == 1) trade[i][0]++;
if (trade[i][j] == 2) trade[i][5]++;
}
}
// Before Trade----------------------------
// City value
for (int i=0; i<10; i++) {
beforeSumA += value[i][owner[i][0]];
beforeSumB += value[i][owner[i][5]];
}
// Cash value
beforeSumA += cashA * cashRate / 100;
beforeSumB += cashB * cashRate / 100;
// Mortgage
for (int i=0; i<10; i++)
for (int j=1; j<=4; j++)
if (mortgage[i][j] == true) {
if (owner[i][j] == 1) beforeMortgageA++;
if (owner[i][j] == 2) beforeMortgageB++;
}
beforeSumA -= mortgagePrice * beforeMortgageA;
beforeSumB -= mortgagePrice * beforeMortgageB;
// result
resultBefore = beforeSumA - beforeSumB;
// After Trade-----------------------------
// City value
for (int i=0; i<10; i++) {
afterSumA += value[i][trade[i][0]];
afterSumB += value[i][trade[i][5]];
}
// Cash value
afterSumA += changeA * cashRate / 100;
afterSumB += changeB * cashRate / 100;
// Mortgage
for (int i=0; i<10; i++)
for (int j=1; j<=4; j++)
if (mortgage[i][j] == true) {
if (trade[i][j] == 1) afterMortgageA++;
if (trade[i][j] == 2) afterMortgageB++;
}
afterSumA -= mortgagePrice * afterMortgageA;
afterSumB -= mortgagePrice * afterMortgageB;
resultAfter = afterSumA - afterSumB;
// ================================ Print Answer ===================================
if (resultAfter - resultBefore >= 0)
cout << "YES";
else
cout << "NO";
printChart();
return 0;
}
void printChart() {
printf("\n\n");
printf(" | Before Trade | After Trade\n");
printf(" | Me | Rival | Me | Rival \n");
printf(" |Origin Convert|Origin Convert|Origin Convert|Origin Convert\n");
printf("--------------------------------------------------------------------------\n");
for (int i=0; i<10; i++)
printf(" City %c | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n", i+65,
owner[i][0], value[i][owner[i][0]], owner[i][5], value[i][owner[i][5]],
trade[i][0], value[i][trade[i][0]], trade[i][5], value[i][trade[i][5]]);
printf("--------------------------------------------------------------------------\n");
printf(" Cash | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n",
cashA, cashA*cashRate/100, cashB, cashB*cashRate/100,
changeA, changeA*cashRate/100, changeB, changeB*cashRate/100);
printf(" Mortgage | %6d %5d | %6d %5d | %6d %5d | %6d %5d \n",
beforeMortgageA, beforeMortgageA*mortgagePrice, beforeMortgageB, beforeMortgageB*mortgagePrice,
afterMortgageA, afterMortgageA*mortgagePrice, afterMortgageB, afterMortgageB*mortgagePrice);
printf("--------------------------------------------------------------------------\n");
printf(" Sum | %6d | %6d | %6d | %6d\n",
beforeSumA, beforeSumB, afterSumA, afterSumB);
printf(" Distance | %6d | %6d\n", resultBefore, resultAfter);
}