1초 단위마다 바뀐 위치에서 얻을 수 있는 최대값을 끝날때까지 더해주면 된다.
최대값 구하는 방법 :
1. A와 B가 현재 위치에서 가능한 충전량의 최대값 1등, 2등을 찾는다.
2.
A가 0개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우
A가 1개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우
A가 2개 연결된 경우 - B가 0개 연결된 경우, 1개 연결된 경우, 2개 연결된 경우
9가지 경우로 나누어 최대값을 찾아 더해준다.
#include <stdio.h> #include <algorithm> using namespace std; struct Battery { int x; int y; int c; //충전 범위 int p; //처리량 }; struct Node { int x; int y; }; int t, m, a, res; int a_move[102]; int b_move[102]; Battery bs[10]; int dx[] = { 0, 0, 1, 0, -1 }; int dy[] = { 0, -1, 0, 1, 0 }; Node a_cur, b_cur; int getDist(Node node, int idx) { int x = abs(node.x - bs[idx].x); int y = abs(node.y - bs[idx].y); return x + y; } void addResult(int a_first, int a_first_idx, int a_second, int b_first, int b_first_idx, int b_second) { //a가 0개 if (a_first == 0) { res += b_first; } //a가 1개 else if (a_first != 0 && a_second == 0) { //b가 0개 if (b_first == 0) { res += a_first; } //b가 1개 else if (b_first != 0 && b_second == 0) { if (a_first_idx == b_first_idx) { res += a_first; } else { res += a_first + b_first; } } //b가 2개 else if (b_second != 0) { if (a_first_idx == b_first_idx) { res += a_first + b_second; } else { res += a_first + b_first; } } } //a가 2개 else if (a_second != 0) { //b가 0개 if (b_first == 0) { res += a_first; } //b가 1개 else if (b_first != 0 && b_second == 0) { if (a_first_idx == b_first_idx) { res += b_first + a_second; } else { res += b_first + a_first; } } //b가 2개 else if (b_second != 0) { if (a_first_idx == b_first_idx) { res += a_first + max(a_second, b_second); } else { res += a_first + b_first; } } } } int main() { scanf("%d", &t); for (int tc = 1; tc <= t; tc++) { scanf("%d %d", &m, &a); for (int i = 0; i < m; i++) { scanf("%d", &a_move[i]); } for (int i = 0; i < m; i++) { scanf("%d", &b_move[i]); } for (int i = 0; i < a; i++) { scanf("%d %d %d %d", &bs[i].x, &bs[i].y, &bs[i].c, &bs[i].p); } res = 0; //위치 초기화 a_cur.x = 1; a_cur.y = 1; b_cur.x = 10; b_cur.y = 10; //처음 위치에서 충전량 계산 int a_first = 0; int a_first_idx = 0; int a_second = 0; int b_first = 0; int b_first_idx = 0; int b_second = 0; for (int i = 0; i < a; i++) { int dist = getDist(a_cur, i); if (bs[i].c >= dist) { if (a_first < bs[i].p) { a_second = a_first; a_first = bs[i].p; a_first_idx = i; } else { if (a_second < bs[i].p) { a_second = bs[i].p; } } } dist = getDist(b_cur, i); if (bs[i].c >= dist) { if (b_first < bs[i].p) { b_second = b_first; b_first = bs[i].p; b_first_idx = i; } else { if (b_second < bs[i].p) { b_second = bs[i].p; } } } } addResult(a_first, a_first_idx, a_second, b_first, b_first_idx, b_second); //이동 후 충전량 계산 for (int i = 0; i < m; i++) { a_cur.x = a_cur.x + dx[a_move[i]]; a_cur.y = a_cur.y + dy[a_move[i]]; b_cur.x = b_cur.x + dx[b_move[i]]; b_cur.y = b_cur.y + dy[b_move[i]]; a_first = 0; a_first_idx = 0; a_second = 0; b_first = 0; b_first_idx = 0; b_second = 0; for (int j = 0; j < a; j++) { int dist = getDist(a_cur, j); if (bs[j].c >= dist) { if (a_first < bs[j].p) { a_second = a_first; a_first = bs[j].p; a_first_idx = j; } else { if (a_second < bs[j].p) { a_second = bs[j].p; } } } dist = getDist(b_cur, j); if (bs[j].c >= dist) { if (b_first < bs[j].p) { b_second = b_first; b_first = bs[j].p; b_first_idx = j; } else { if (b_second < bs[j].p) { b_second = bs[j].p; } } } } addResult(a_first, a_first_idx, a_second, b_first, b_first_idx, b_second); } printf("#%d %d\n", tc, res); } }
'SWEA::문제풀이' 카테고리의 다른 글
5650 핀볼 게임 (0) | 2018.10.16 |
---|---|
5648 원자 소멸 시뮬레이션 (0) | 2018.10.08 |
공통조상 (0) | 2018.09.06 |
균형점 (0) | 2018.09.06 |
최대 상금 (0) | 2018.09.06 |