BOJ 2160 - 그림 비교

문제

N개의 5×7 그림이 주어질 때, 서로 다른 칸의 수가 가장 적은 두 그림의 번호를 출력하라.

입력

첫째 줄에 그림 수 N, 이후 각 그림이 5줄 7문자로 주어진다.

출력

가장 비슷한 두 그림의 번호를 출력한다.

예제

입력	출력
(N개의 5x7 그림)	(두 번호)

풀이

모든 그림 쌍에 대해 5×7 칸을 비교하여 차이가 최소인 쌍을 찾는다.

N개의 그림을 3차원 배열에 저장한다
모든 쌍 (i, j)에 대해 35칸을 비교하여 다른 칸의 수를 센다
다른 칸의 수가 최소인 쌍의 번호를 기록한다
최소 쌍의 번호를 출력한다

핵심 아이디어: 그림 크기가 5×7=35로 고정되어 비교 비용이 상수이므로, O(N^2)개의 쌍을 모두 비교해도 충분하다.

코드

#include <stdio.h>
 
char arr[23][23][230];
int main()
{
  int n, ans, min = 36, mini = 0, minj = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
  {
    for (int k = 1; k <= 5; k++)
    {
      for (int j = 1; j <= 7; j++)
      {
        scanf(" %c", &arr[k][j][i]);
      }
    }
  }
  for (int i = 1; i <= n - 1; i++)
  {
    for (int j = i + 1; j <= n; j++)
    {
      ans = 0;
      for (int a = 1; a <= 5; a++)
      {
        for (int b = 1; b <= 7; b++)
        {
          if (arr[a][b][i] != arr[a][b][j])
          {
            ans++;
          }
        }
      }
      if (ans < min)
      {
        min = ans;
        mini = i;
        minj = j;
      }
    }
  }
  printf("%d %d", mini, minj);
}

복잡도

시간: O(N^2 * 35)
공간: O(N * 35)

문제