문제 문제 읽기 해결 단순 구현 문제를 잘 읽자(3개 초과 설치시 계산할 필요가 없다) 가로에 최대 5개 설치 가능, 세로 30개 이므로 설치 가능한 경우의 수는 $150 C 3 \approx 550000$ 사다리 검사는 $O(N \cdot H)$, 최악의 경우 시간복잡도는 $O(550000 \cdot N \cdot H)$ 소스코드 /* Prob https://www.acmicpc.net/problem/15684 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; static int IMP = INT_MAX; int N, M, H, ans = IMP; bool lad[15][35]; bool isAns()..
문제 문제 읽기 해결 단순 구현 문제를 잘 읽자(로봇 청소기 좌표[r, c]는 x, y순이 아니다) 소스코드 /* Prob https://www.acmicpc.net/problem/14503 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, m, r, c, d, ans; int mmap[50][50]; int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; int main(void) { freopen("input.txt", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); c..
문제 문제 읽기 해결 단순 구현 나머지 연산으로 회전을 대체 소스코드 /* Prob https://www.acmicpc.net/problem/14891 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int k; int gear[4][8]; int now[4]; int main(void) { freopen("input.txt", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); string line; for(int i = 0; i > line; for(int j = 0; j < 8; j++..
문제 문제 읽기 해결 단순 구현 소스코드 /* Prob https://www.acmicpc.net/problem/14890 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, l, ans; int mmap1[100][100], mmap2[100][100]; void count(int mmap[100][100]) { for(int y = 0; y < n; y++) { bool possible = true; int flat = 1; for(int x = 1; x < n; x++) { if(mmap[y][x] == mmap[y][x - 1]) flat++; else if(mmap[y][x] - mm..
문제 문제 읽기 해결 브루트포스 모든 이동 경우의 수를 생각 시간복잡도: $O(n^2\cdot 4^5)\approx O(409,600)$ 소스코드 /* Prob https://www.acmicpc.net/problem/12100 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, ans; int mmap[22][22]; int dx[4] = {1 , -1, 0, 0}, dy[4] = {0, 0, 1 , -1}; void move(int dir) { bool check[22][22] = {false, }; // block only combined once at a try for(int i = (..
문제 문제 읽기 해결 브루트포스 m개의 치킨집 조합을 구하고 각 경우마다의 최소 치킨거리를 구함 치킨집 조합의 가짓수: $\frac{13!}{m!\cdot(13-m)!} < 1800$ 시간복잡도: $O(1800\cdot 2n\cdot m)$ 소스코드 /* Prob https://www.acmicpc.net/problem/15686 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, m, ans = INT_MAX; int mmap[50][50]; vector chics, homes; bool chk[13]; void solve() { int sum = 0; for(pair home : homes..
문제 문제 읽기 해결 재귀로 해결 $O(2\cdot n )$ 소스코드 /* Prob https://www.acmicpc.net/problem/14889 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, statMin = INT_MAX, aStat, bStat; vector aTeam, bTeam; int stat[20][20]; void rec(int memIdx) { if(memIdx == n) { statMin = min(statMin, abs(aStat - bStat)); return; } if(aTeam.size() < n / 2) { int cp = aStat; aTeam.push_..
문제 문제 읽기 해결 재귀로 해결 $O(4\cdot n )$ 소스코드 /* Prob https://www.acmicpc.net/problem/14888 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int n, resMax = INT_MIN, resMin = INT_MAX; int a[11], op[4]; void rec(int idx, int res) { if(idx == n) { // end Case resMax = max(res, resMax); resMin = min(res, resMin); return ; } for(int i = 0; i < 4; i++) { if(op[i] == 0) co..
Comment