AtCoder Beginner Contest 173 후기

 

https://atcoder.jp/contests/abc173

AtCoder Beginner Contest 173 - AtCoder

 

---

엣 코더는 물론 단점도 있지만 9시에 시작한다는 점과 대회가 끝나고 10분 내외로 레이팅 반영이 된다는 건 정말 좋네요.

일요일 10시40분에 대회를 마치고 레이팅과 해설을 확인하고 한 주의 끝을 뿌듯하게 마친다는 건 좋은 습관인 것 같습니다.

이번 대회는 비교적 빠른 시간에 D문제까지 풀 수 있어서 결과가 좋았습니다. 이제 문제를 살펴보면,

A-거스름돈을 계산하는 문제인데, 혹시모를 오류 케이스를 시간 내서 찾기보단 그냥 반복문으로 해결했습니다.

int main()
{
	int N;
	cin >> N;
	for (int i = 0;; i += 1000) {
		if (i <= N&&N <= i + 1000) {
			cout << (i + 1000 - N);
			break;
		}
	}
}

B-마찬가지로 매우 쉬운 문제입니다. 더 깔끔하게 코드를 짤수있지만 시간제한이 있는 대회 특성상 약간의 하드코딩으로 짠 문제입니다.

int main()
{
	int N, visited[4] = { 0, };
	cin >> N;
	while (N--) {
		string s;
		cin >> s;
		if (s == "AC")visited[0]++;
		else if (s == "WA")visited[1]++;
		else if (s == "TLE")visited[2]++;
		else visited[3]++;
	}
	cout << "AC x " << visited[0] << "\n";
	cout << "WA x " << visited[1] << "\n";
	cout << "TLE x " << visited[2] << "\n";
	cout << "RE x " << visited[3] << "\n";
}

C-영어 해석이 까다로었던 기억이 나네요.. bit연산으로 깔끔하게 구현할 수 있습니다.

int main()
{
	int N, M, K, ans = 0;
	int board[6][6] = { 0, };
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			char c;
			cin >> c;
			if (c == '#')board[i][j] = 1;
		}

	for (int bitsY = 0; bitsY < (1 << N); bitsY++) {
		for (int bitsX = 0; bitsX < (1 << M); bitsX++) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				if (bitsY&(1 << i))continue;
				for (int j = 0; j < M; j++) {
					if (bitsX&(1 << j))continue;
					if (board[i][j] == 1)cnt++;
				}
			}
			if (cnt == K)ans++;
		}
	}

	cout << ans;
}

D-그리디 알고리즘 문제였습니다. 이런 문제가 규칙을 못 찾아내면 참 까다로운 문제인데,

직접 손으로 그려보면 가장 최적의 해가 어떻게 나오게 되는지 알 수 있습니다. 우선 행복도는 양옆의 값의 최솟값이므로

내림차순으로 정렬 후 앞에 있는 행복도가 큰 순서대로부터 원에 들어가야 한다는 것을 알 수 있습니다.

그렇게 순서대로 원에 삽입을 하다 보면 행복도의 합계는 다음과 같다는 것을 알 수 있습니다.

행복도를 a, b, c, d, e라 할 때(내림차순) 최댓값은 a+b+b+c+c가 된다.

즉, v0+v1+v1+v2+v2+v3+v3+.... 의 더하는 행위를 N-1번 반복하면 되는 겁니다. 

typedef long long ll;

int main()
{
	int N;
	ll sum = 0;
	cin >> N;
	vector<int>v(N);
	for (auto&i : v)cin >> i;
	sort(v.rbegin(), v.rend());
	int idx = 1, plusN = 1;
	sum += v[0];
	while (plusN < N-1) {
		sum += v[idx];
		if (++plusN == N - 1)break;
		sum += v[idx];
		idx++,plusN++;
	}
	cout << sum;
}

E-여기서부턴 대회 시간 내에 못 푼 문제인데, 이 문제 개인적으로 아쉬웠습니다. 분명히 예전에 백준에서 풀었던 기억이 나는데, 풀이 방법이 생각이 안 나서.. 대회 끝나고 찾아보니까 제가 비슷하게 풀었던 문제는 이번 E문제의 easy버전이었습니다. 2개, 3개만 선택하는 경우라서 무식하게 해결할 수 있었죠.

https://www.acmicpc.net/problem/14753

14753번: MultiMax

다음 문제를 먼저 풀고 이번 E문제를 푸시는 걸 추천해드립니다. 해결방법은 case work(케이스 나누기)입니다.

const long long mod = 1e9 + 7;

int main()
{
  int N, K;
  cin >> N >> K;

  vector<long long> pos, neg;
  for(int i = 0; i < N; i++){
    long long A;
    cin >> A;
    if(A >= 0) pos.push_back(A);
    else neg.push_back(-A);
  }

  int n_pos = int(pos.size()), n_neg = int(neg.size());

  long long ans = 1;

  if(K == N){
    for(int i = 0; i < n_pos; i++){
      ans *= pos[i];
      ans %= mod;
    }

    for(int i = 0; i < n_neg; i++){
      ans *= -neg[i];
      ans %= mod;
    }
  }else if(n_neg == N && (K & 1)){
    sort(neg.begin(), neg.end());

    ans = -1;
    for(int i = 0; i < K; i++){
      ans *= neg[i];
      ans %= mod;
    }
  }else{
    sort(pos.begin(), pos.end(), greater<long long>());
    sort(neg.begin(), neg.end(), greater<long long>());

    int idx_pos = 0, idx_neg = 0;

    if(K & 1){
      --K;
      ans = pos[idx_pos++];
    }

    for(int i = 0; i < K; i += 2){
      if(idx_pos + 1 < n_pos && idx_neg + 1 < n_neg){
        if(pos[idx_pos] * pos[idx_pos + 1] < neg[idx_neg] * neg[idx_neg + 1]){
          ans *= neg[idx_neg] * neg[idx_neg + 1] % mod;
          idx_neg += 2;
        }
        else{
          ans *= pos[idx_pos] * pos[idx_pos + 1] % mod;
          idx_pos += 2;
        }
      }
      else if(idx_pos + 1 < n_pos){
        ans *= pos[idx_pos] * pos[idx_pos + 1] % mod;
        idx_pos += 2;
      }
      else{
        ans *= neg[idx_neg] * neg[idx_neg + 1] % mod;
        idx_neg += 2;
      }

      ans %= mod;
    }
  }

  cout << (ans + mod) % mod;

  return 0;
}

 까다로운 부분은 크게 두 가지였습니다. 음수일 때 mod연산은 (a+mod)% mod형태여야 한다는 점, 음수와 양수가 섞였을 때 곱셈의 최대화를 어떻게 그리디 하게 접근할지.

F-추가 예정