문제 분석
https://www.acmicpc.net/problem/1089
5*4N-1의 배열이 주어지고
주어진 배열에서 # 으로 표시되는 부분이 전구가 켜져있는 곳, 그리고 .으로 표시되는 곳이 전구가 꺼진 곳이다.
여기서, 전구가 꺼진 곳은 고장난 곳일 수 있다.
주어진 배열에서 꺼진 전구를 다시 켤 수 있다고 할 때 켜진 전구로 표현되는 모든 숫자들의 평균을 구하는게 문제다.
예시를 보면 이해가 편하다
###...#.###.###.#.#.###.###.###.###.###
#.#...#...#...#.#.#.#...#.....#.#.#.#.#
#.#...#.###.###.###.###.###...#.###.###
#.#...#.#.....#...#...#.#.#...#.#.#...#
###...#.###.###...#.###.###...#.###.###이런식으로 배열이 주어지고
각 5*3 박스마다 숫자가 표현되고 각 숫자박스 끼리는 .으로 구성된 5*1 박스로 구분된다
꺼져있는 전구를 켰을 때 숫자가 만들어지는 지 판단하는 것보단 5*3 박스의 위치마다 전구가 켜져있다면 만들어질 수 없는 수
예를 들어 0,0 위치에 전구가 켜져있다면 1은 해당 숫자 박스에서 만들어 낼 수 없는 수가 된다.
이런 불가능한 수들을 각 위치마다 저장하고
각 숫자 박스마다 전구가 켜져있는 곳에서 만들 수 없는 수들의 집합을 구하고
0~9 중 이 집합에 포함되지 않는 수가 해당 숫자 박스에서 만들어낼 수 있는 수가 된다.
다음으론 이 가능한 숫자 집합들로 만들어낼 수 있는 모든 수의 평균을 구해야 한다.
만약 전체 숫자들을 다 구하고 평균을 내면 10^9의 반복을 해야 할 수 있기에 (모든 전구가 꺼져있는 n=9인 배열) 다른 방식으로 평균을 구해보자.
각 박스에서 만들어낸 숫자가 4,8이라고 해보자.
그리고 그 다음 박스에서 만들어낸 숫자가 2,3 이라 해보자.
(물론 불가능하다)
그러면 만들어낼 수 있는 수는 42 43 82 83이다. 평균은 62.5가 된다.
그런데, 굳이 모든 수를 구하는게 아닌 각 자리수 별로 평균을 내고 더해준다면
즉, (4+8)/2 *10 + (2+3)/2 * 1 이렇게 구해줘도 똑같은 식이 형성된다.
따라서, 우리는 굳이 최대 10^9 번의 반복을 할 필요 없이 숫자 박스에서 구하자마자 평균을 낼 수 있게 된다.
코드
import java.util.*;
public class Main {
static boolean[][] isTurnOn;
static Set[][] impossibleNumSet;
public static void main(String[] args) {
impossibleNumSet = new Set[5][3];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
impossibleNumSet[i][j] = new HashSet<>();
}
}
impossibleNumSet[1][1].add(0);
impossibleNumSet[2][1].add(0);
impossibleNumSet[3][1].add(0);
impossibleNumSet[0][0].add(1);
impossibleNumSet[1][0].add(1);
impossibleNumSet[2][0].add(1);
impossibleNumSet[3][0].add(1);
impossibleNumSet[4][0].add(1);
impossibleNumSet[0][1].add(1);
impossibleNumSet[1][1].add(1);
impossibleNumSet[2][1].add(1);
impossibleNumSet[3][1].add(1);
impossibleNumSet[4][1].add(1);
impossibleNumSet[1][0].add(2);
impossibleNumSet[1][1].add(2);
impossibleNumSet[3][1].add(2);
impossibleNumSet[3][2].add(2);
impossibleNumSet[1][0].add(3);
impossibleNumSet[1][1].add(3);
impossibleNumSet[3][0].add(3);
impossibleNumSet[3][1].add(3);
impossibleNumSet[0][1].add(4);
impossibleNumSet[1][1].add(4);
impossibleNumSet[3][0].add(4);
impossibleNumSet[3][1].add(4);
impossibleNumSet[4][0].add(4);
impossibleNumSet[4][1].add(4);
impossibleNumSet[1][1].add(5);
impossibleNumSet[1][2].add(5);
impossibleNumSet[3][0].add(5);
impossibleNumSet[3][1].add(5);
impossibleNumSet[1][1].add(6);
impossibleNumSet[1][2].add(6);
impossibleNumSet[3][1].add(6);
impossibleNumSet[1][0].add(7);
impossibleNumSet[2][0].add(7);
impossibleNumSet[3][0].add(7);
impossibleNumSet[4][0].add(7);
impossibleNumSet[1][1].add(7);
impossibleNumSet[2][1].add(7);
impossibleNumSet[3][1].add(7);
impossibleNumSet[4][1].add(7);
impossibleNumSet[1][1].add(8);
impossibleNumSet[3][1].add(8);
impossibleNumSet[1][1].add(9);
impossibleNumSet[3][0].add(9);
impossibleNumSet[3][1].add(9);
Scanner sc = new Scanner(System.in);
//0~9
int n = Integer.parseInt(sc.nextLine());
isTurnOn = new boolean[5][4*n-1];
for (int i = 0; i < 5; i++) {
char[] charArray = sc.nextLine().toCharArray();
for (int j = 0; j < charArray.length; j++) {
isTurnOn[i][j] = charArray[j] == '#';
}
}
double[] possibleNumAvg = new double[n];
for (int i = 0; i < n; i++) {
Set<Integer> possibleNumbers = getPossibleNumbers(4*i);
if(possibleNumbers.isEmpty()){
System.out.println("-1");
return;
}
int sum=0;
for (Integer possibleNumber : possibleNumbers) {
sum+=possibleNumber;
}
possibleNumAvg[i] = (double) sum /possibleNumbers.size();
}
double totalAvg = 0;
int multi = 1;
for(int i=n-1 ; i>=0 ; i--){
totalAvg += possibleNumAvg[i]*multi;
multi*=10;
}
System.out.println(totalAvg);
}
static Set<Integer> getPossibleNumbers(int start){
Set<Integer> impossibleNumbers = new HashSet<>();
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
if(isTurnOn[i][j+start])
impossibleNumbers.addAll(impossibleNumSet[i][j]);
}
}
Set<Integer> possibleNumbers = new HashSet<>();
for (int i = 0; i < 10; i++) {
if(impossibleNumbers.contains(i))
continue;
possibleNumbers.add(i);
}
return possibleNumbers;
}
}
