9088. 다이아몬드

링크

난이도 : d4
정답률 : _41%

설계

자료구조

다이아몬드 무게의 범위가 1 ~ 10,000 이므로 10001 크기의 배열을 선언한다.

알고리즘

다이아몬드 무게 입력시 무게를 index로 하는 배열의 count를 증가시킨다.

배열을 순회하며 현재 inex ~ 현재 inex + K 까지의 수를 count하며 max를 갱신한다.

정리

고생한 점

문제의 이해가 어려웠다.

처음엔 다이아몬드 쌍을 구하는 줄 알고, 정답이 모두 짝수로 나오는 경우로 생각함.

그것이 아닌 묶음이므로 한정된 범위 내의 다이아몬드의 최대 갯수를 구하는 문제였다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solution(int test_case) {
  int answer = 0, N, K, temp, MAX = 0, MIN = 10000;
  int dias[10001] = {
      0,
  };

  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    cin >> temp;
    dias[temp] += 1;
    MAX = max(MAX, temp);
    MIN = min(MIN, temp);
  }

  for (int i = MIN; i <= MAX; i++) {
    if (dias[i] == 0) {
      continue;
    }
    temp = 0;
    for (int j = i; j <= min(MAX, i + K); j++) {
      temp += dias[j];
    }
    answer = max(answer, temp);
  }

  cout << "#" << test_case << " " << answer << "\n";
}

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}

링크

난이도 : d4
정답률 : _12%

설계

제약조건

점은 최대 10개

answer의 최대값

총 이동거리 diff의 값의 max는 2 X 10^9 이다.

1부터 10^5까지 더하는 경우 max를 충분히 넘기고도 남으므로

절대 모든점이 원점으로 돌아가지 못하는 경우를 제외하고는

answer의 값은 10^5를 넘지 않는다.

원점으로 이동할 수 없는 경우

모든 점의 원점으로부터의 거리가 짝수이거나 홀수여야 한다.
이 외에는 전부 원점으로 이동할 수 없다.

이동 처리

점의 x 좌표와 y좌표의 원점으로 부터의 거리를 구해 더한다.

이 더한 값을 diff라고 하자.

i = 0부터 증가시키며 각 점의 떨어진 길이에서 뺀다.

먼저 원점에 도착한 점의 경우 다른 점이 도착할 때 까지 +1, -1을 반복한다고 가정하자.

정리

내 코드 : 106 ms;
빠른 코드 : 10 ms;

처음에 각 점들의 diff를 구하고, 전부 홀수인지 짝수인지 판별한다.

이 조건을 만족하지 않으면 -1

전부 짝수이거나 홀수인 경우, 먼저 원점에 도달한 점은,
다른 점이 도착할 때까지 의미없는 이동을 반복할 것이다.

따라서 가장 큰 diff인 경우만 판별하면 된다.

모든 점의 diff == 0일수 있기 때문에 answer=0부터 for문을 수행한다.

max_diff에서 answer를 빼가면서, max_diff가 0 이하가 되었을 때 다음 두가지로 나뉜다.

• max_diff가 홀수(짝수)인데, 현재 answer가 홀수(짝수)
• max_diff가 홀수(짝수)인데, 현재 answer가 짝수(홀수)

위의 경우는 다음 answer, 그 다음 answer의 거리만큼 이동시켜 주어야 원점에 도달한다.
아래의 경우는 다음 answer의 거리만큼만 이동시켜 주면 원점에 도달한다.

고생한 점

계속 시간초과가 발생했다.

max_diff만 비교하는 경우에도 100 ms 이상 걸리는 것을 볼 때,

테스트 케이스 1000개는 우습게 볼 것이 아니다.

#include <math.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
bool canMove(vector<long long>& diffs) {
  int odd = 0, even = 0;
  for (long long diff : diffs) {
    if (diff % 2 == 1) {
      odd++;
    } else {
      even++;
    }
  }
 
  if (even == 0 || odd == 0) {
    return true;
  }
  return false;
}
 
void solution(int test_case) {
  int answer = 0;
  vector<long long> diffs;
  long long max_diff = 0;
  int N;
  cin >> N;
 
  for (int i = 0; i < N; i++) {
    long long x, y;
    cin >> x >> y;
    long long diff = abs(0 - x) + abs(0 - y);
 
    diffs.push_back(diff);
    max_diff = max(max_diff, diff);
  }
 
  if (!canMove(diffs)) {
    answer = -1;
    cout << "#" << test_case << " " << answer << "\n";
    return;
  }
 
  for (answer = 0; answer < 100000; answer++) {
    max_diff -= answer;
 
    if (max_diff <= 0) {
      break;
    }
  }
 
  max_diff = -max_diff % 2;
 
  if (max_diff != 0) {
    if (max_diff == (answer + 1) % 2) {
      answer += 1;
    } else {
      answer += 2;
    }
  }
 
  cout << "#" << test_case << " " << answer << "\n";
}
 
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  int T;
  cin >> T;
 
  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }
 
  return 0;
}

8934. 팰린드롬 공포증

링크

난이도 : d4
정답률 : _42%

설계

어떤 경우에라도 팰린드롬이 나타나는 경우

• aba
• aaba
• aabca
• aabaa
• aabbca

절대 팰린드롬을 만들지 않기 위해 abc순으로 계쏙 나열한다고 하자.

(가장 많이 나온 알파벳을 a, 그 다음 많이 나온 알파벳을 b라고 할 때)

abc로 만들고 남은 알파벳의 수는

a의 남은 개수 : count(a)-count(c)

무조건 팰린드롬이 나오는 경우는

count(a_left) > 1 인 경우이다.

a가 2개 이상인 경우 b의 개수가 아무리 많아도,
양 끝에 a를 넣으면 팰린드롬이 되기 때문이다.

정리

내 코드 : 32 ms;
빠른 코드 : 25 ms; Mon Dec 02 2019 23:05:35 GMT+0900 (한국 표준시) 기준

문제의 설명이 너무 적어 규칙을 찾기 어려웠던 문제.

풀이법

1. 펠린드롬이 무조건 나오는 경우를 만들어 본다.
2. a, b, c의 갯수들을 count한 수를 비교해가며 정답의 갯수를 늘려간다.
3. 펠린드롬이 무조건 나오지 않는 경우를 남은 a,b,c의 수를 카운트한다.

3번에서 abc순으로 계속 나열할 때,
남은 인자들로 팰린드롬을 만들지 못하면 YES인 것을 확인.

고생한 점

문제의 설명이 너무 적었다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalin(string word) {
  int length = word.length();

  string first = word.substr(0, length / 2);
  string second = word.substr((length + 1) / 2, length);

  reverse(second.begin(), second.end());

  for (int index = 0; index < length / 2; index++) {
    if (first[index] == '?' || second[index] == '?') {
      continue;
    }
    if (first[index] != second[index]) {
      return false;
      break;
    }
  }
  return true;
}

void solution(int test_case) {
  string answer = "YES";
  string str;
  vector<int> count;
  count.resize(3, 0);

  cin >> str;

  for (char c : str) {
    count[c - 'a']++;
  }

  sort(count.begin(), count.end());

  count[2] -= count[0];

  if (count[2] > 1) {
    answer = "NO";
  }

  cout << "#" << test_case << " ";
  cout << answer << "\n";
}

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}