문제
BOJ 1089: 스타트링크 타워 https://www.acmicpc.net/problem/1089
풀이
-
block[n][i][j]에 입력 받은 숫자를 구분하여 입력 형식 그대로 저장한다.예시)
위의 형식으로 입력이 들어왔다면,
block[0][ ][ ]에는
이렇게 저장된다.
-
입력받은 값을 보고 해당 자리에 올 수 있는 숫자를 찾는다.
- 위의 표에서 빨간 색이 있는 위치의 숫자는 각 좌표에
#가 있을 때불가능한 숫자이다 check(n, i, j)메소드를 사용하여impossibleNum[ ][ ] 배열에 불가능한 숫자는 true로 표시한다.
- 위의 표에서 빨간 색이 있는 위치의 숫자는 각 좌표에
-
impossibleNum[ ][ ] 배열을 사용하여 답을 구한다.- 모든 수를 구해 총합을 구하면 9자리 모두
.이 들어왔을 때시간 초과가 날 수 있으므로 아래와 같이 총합을 구해야한다. - https://t-anb.tistory.com/11 블로그를 참고하면 이해가 더 쉬울 수 있다.
- 구현 방법은 아래 코드 부분에서 주석을 함께 보면 된다.
예시를 통해 보는 최종 답을 구하는 과정- N이 3일 때
- 각 자리에 가능한 숫자가 아래와 같을 때
- 위의 상황일 때,
- 100의 자리(첫 번째 자리)에 올 수 있는 수는 1, 2, 3, 4 이다.
- 10의 자리(두 번째 자리)에 올 수 있는 수는 5, 6 이다.
- 1의 자리(세 번째 자리)에 올 수 있는 수는 7, 8, 9 이다.
- 위의 상황에서 만들 수 있는 수의 갯수는
4 X 2 X 3 = 24이다. 총합을 누적할 때 아래와 같은 원리로 구한다.
- 위에서 100이 6개, 200이 6개, 300이 6개, 400이 6개 필요하다.
- 이런 연산을 10의 자리, 1의 자리에서도 해서 모두 더하면 총합이 나온다.
- 모든 수를 구해 총합을 구하면 9자리 모두
코드
import java.util.*;
import java.io.*;
public class Programmers {
static int N;
static char[][][] block; // 왼쪽부터 0번째 블럭(숫자)
static boolean[][] impossibleNum; // 불가능한 수를 체크할 배열(제외하기 위해)
static double sum;
static double now;
static double cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
block = new char[N][5][3];
// 입력값을 블럭(숫자) 별로 3차원 배열에 저장함
for(int t=0; t<5; t++) {
String line = br.readLine();
int n=0;
int k=0;
int j=0;
while(k < 3*N + N-1) {
char c = line.charAt(k);
if(k % 4 == 3) {
k++;
continue;
}
if(j > 2) {
j = 0;
n++;
}
block[n][t][j] = c;
j++;
k++;
}
}
// 불가능한 수와 가능한 수를 구분하여 체크
impossibleNum = new boolean[N][10];
for(int n=0; n<N; n++) {
for(int i=0; i<5; i++) {
for(int j=0; j<3; j++) {
if(block[n][i][j] == '#') {
check(n, i, j);
}
}
}
}
sum = 0;
now = 0;
cnt = 1;
answer();
double ans = sum / cnt;
System.out.println(ans);
}
static void answer() {
double numCnt = 0;
double numSum = 0;
double totalCnt = 1;
// 가능한 모든 수의 갯수 구함
for(int n=0; n<N; n++) {
for(int i=0; i<10; i++) {
if(!impossibleNum[n][i]) {
numCnt++;
}
}
totalCnt *= numCnt;
}
// 1 자리, 10 자리, 100 자리 .... 숫자를 곱해서 자연수로 만들 때 사용할 변수
int multi = 1;
for(int i=1; i<N; i++) {
multi *= 10;
}
// 찾아놓은 가능한 숫자로 계산
for(int n=0; n<N; n++) {
numCnt = 0;
numSum = 0;
for(int i=0; i<10; i++) {
if(impossibleNum[n][i]) continue;
numCnt++;
numSum += i * multi;
}
double a = totalCnt / numCnt;
sum += numSum * a;
multi /= 10;
}
cnt = totalCnt;
}
static void check(int n, int i, int j) {
/*
* n: n번째 블럭(숫자)
* i: 행 순서
* j: 열 순서
*/
switch(i) {
case 0:
if(j == 0) {
impossibleNum[n][1] = true;
}
if(j == 1) {
impossibleNum[n][1] = true;
impossibleNum[n][4] = true;
}
if(j == 2) {
}
break;
case 1:
if(j == 0) {
impossibleNum[n][1] = true;
impossibleNum[n][2] = true;
impossibleNum[n][3] = true;
impossibleNum[n][7] = true;
}
// (1, 1) 위치에 "#" 가 있는 숫자는 없다.
// -1 출력 후 바로 종료
if(j == 1) {
System.out.println(-1);
System.exit(0);
}
if(j == 2) {
impossibleNum[n][5] = true;
impossibleNum[n][6] = true;
}
break;
case 2:
if(j == 0) {
impossibleNum[n][1] = true;
impossibleNum[n][7] = true;
}
if(j == 1) {
impossibleNum[n][0] = true;
impossibleNum[n][1] = true;
impossibleNum[n][7] = true;
}
if(j == 2) {
}
break;
case 3:
if(j == 0) {
impossibleNum[n][1] = true;
impossibleNum[n][3] = true;
impossibleNum[n][4] = true;
impossibleNum[n][5] = true;
impossibleNum[n][7] = true;
impossibleNum[n][9] = true;
}
// (3, 1) 위치에 "#" 가 있는 숫자는 없다.
// -1 출력 후 바로 종료
if(j == 1) {
System.out.println(-1);
System.exit(0);;
}
if(j == 2) {
impossibleNum[n][2] = true;
}
break;
case 4:
if(j == 0) {
impossibleNum[n][1] = true;
impossibleNum[n][4] = true;
impossibleNum[n][7] = true;
}
if(j == 1) {
impossibleNum[n][1] = true;
impossibleNum[n][4] = true;
impossibleNum[n][7] = true;
}
if(j == 2) {
}
break;
}
}
}정리
- 처음엔 백트래킹을 사용하여 모든 수를 찾아 총합을 구하려고 해서 틀렸었다.
- 평균을 실수로 얻으려면 다른 값들도 정수가 아닌 실수로 해야 구해진다.
