[백준 14889] 스타트와 링크 (삼성 기출)
Algorithm 카테고리의 다른 글
문제
백준 삼성 SW 역량테스트 기출 문제
풀이
최대 20C10 = 184,756 개의 경우의 수가 존재하므로 완전탐색으로 풀기에 충분하다.
코드 GitHub
/****** BAEKJOON 14889 *****/
/***** SAMSUNG SW TEST *****/
/** Solved Date 2021-04-14 */
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<vector<int>> S(N, vector<int>(N, 0));
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j++) {
int s;
cin >> s;
S[i][j] = s;
}
}
vector<bool> isA(N, false);
for(int i = 0; i < N / 2; i++) {
isA[i] = true;
}
int min = 1000000;
while(true) {
int sumA = 0;
int sumB = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(isA[i] && isA[j]) {
sumA += S[i][j];
} else if(!isA[i] && !isA[j]) {
sumB += S[i][j];
}
}
}
int del = sumA - sumB;
if(del == 0) {
min = 0;
break;
} else if(del < 0) {
del = 0 - del;
}
if(del < min) {
min = del;
}
// Combination
int cnt = 1;
bool cngd = false;
for(int i = N - 1; i > 0; i--) {
if(!isA[i] && isA[i - 1]) {
for(int j = 0; j < cnt; j++) {
isA[i + j] = true;
isA[i - 1] = false;
}
cngd = true;
break;
} else if(isA[i]) {
cnt++;
isA[i] = false;
}
}
if(!cngd) {
break;
}
}
cout << min;
}
피드백
std::next_permutation
algorithm 라이브러리의 next_permutation 함수를 이용하면 Combination 로직을 쉽게 구현할 수 있다. (배열을 1과 0으로 채운 뒤에 next_permutation 함수를 호출)
vector 대신 배열 이용
메모리 동적 할당이 필요할 때에 배열 대신 vector를 이용하면 편리하다. 그래서 헷갈리지 않게 C++로 알고리즘 문제를 풀때에는 항상 vector를 이용하기로 했다. 그러나 이 문제와 같이 동적할당이 굳이 필요 없는 간단한 문제일 경우에는 배열을 사용하는 것이 가독성과 효율성(코딩 효율)이 좋다. 앞으로는 굳이 vector를 고집하지 않기로 했다.
댓글남기기