[Java] BOJ1248, 백준 - 맞춰봐

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

1248번: 맞춰봐

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5489	1970	1287	35.494%

문제

규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라고 가르쳐 줬다.

이제 규현이는 0~10까지 수를 알고 있다. 어느 날 자신이 알고 있는 숫자를 까먹지 않으려고 종이에 1~10까지 수를 썻다. (0은 잠시 까먹었다) 규현이의 친구 석원이는 밀덕이다. 계급을 엄청나게 좋아해서, 규현이가 써 놓은 숫자에 이등병 마크인 -를 모두 그렸다. 석원이는 규현이에게 이렇게 말했다. "너, 우리 위대하신 미하엘 칼라시니코프께서 뭐라고 했는지 알아? 단순함과 신뢰성, 그리고 저렴한 가격이 최고야!"

규현이는 그 말을 듣고서 아하 세상에는 음수도 있구나 했다.

이제 규현이가 아는 수는 -10부터 10까지 20개가 되었다. 아차, 0을 빼먹었구나, 21개가 되었다.

근처 사파리에 놀러간 규현이는 사파리 가이드 승환이와 함께 관광을 시작했다. "저기, 사자 1마리가 보이죠? 그 옆이 그 사자 부인이에요. 그러니깐, 1 더하기 1은 2죠" 규현이는 덧셈을 익혔다. "저 사자는 아까 그 사자의 자식 2마리 입니다. 그럼 총 사자는 몇 마리이지요?" 이제 규현이는 1+1을 제외한 다른 덧셈도 할 수 있다. 만세!

인도네시아에 놀러간 규현이는 자바 섬에 방문했다. 자바 섬에는 자바 커피를 재배하는 홍태석 농부가 있었다. 홍태석은 "ㅋㅋㅋ 님 음수와 양수와 0의 차이도 모름?" 하면서 음수와 양수와 0을 설명해주었다.

지금까지 배운 것을 종합해서, 한국으로 돌아오는 비행기에서 규현이는 종이에 수를 N개 썼다. (규현이가 아는 가장 큰 수는 10이기 때문에, 수를 10개까지만 쓸 수 있다.)  그 다음에, 가능한 모든 N*(N+1)/2개의 구간의 합을 구했다. 이 것을 해인이는 행렬로 표현했다.

규현이가 쓴 수를 A라고 하면, A[i]는 규현이가 i번째 쓴 수이다. 그리고, S[i][j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다. 이렇게 배열을 채우면 배열에는 총 N*(N+1)/2개의 문자가 있다. (+, -, 0 중 하나) 이 S 배열이 주어졌을 때, 규현이가 쓴 N개의 수 A를 구해서 출력하면 된다. 규현이는 -10부터 10까지의 정수밖에 모르기 때문에, A도 -10부터 10까지의 정수로만 이루어져 있어야 한다.

 

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.

 

출력

첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 답이 여러 가지 일 경우에는 아무거나 출력하면 된다.

 

<풀이>

부호를 저장할 배열: char[][] s

누적 합을 저장할 배열: int[][] sum

최종 답을 찾았는지 판단하는 변수: success

 

재귀

완료조건: 숫자를 N개 찾았을 때 완료

 

종료조건 : sum 배열과 s배열을 비교하여 부호 조건에 어긋날 경우 종료한다.

 

반복조건 1 - 사용한 수를 1씩 늘려가며 cnt로 전달해준다.

 

1차 코드

import java.io.*;
import java.util.*;

public class Main {
	private static int n;
	private static boolean success;
	private static char[][] s;
	private static int[][] sum;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		String string = br.readLine();
		sum = new int[n][n];
		s = new char[n][n];
		int cnt = -1;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				cnt++;
				s[i][j] = string.charAt(cnt);
			}
		}

		success = false;
		go(0);

	}

	private static void go(int cnt) {
		// 한 번 찾으면 끝나야함
		if (success)
			return;
		// 완료조건: 수열이 N개만큼 쌓였을 때
		if (cnt >= n) {
			success = true;
			for (int i = 0; i < n; i++) {
				System.out.print(sum[i][i] + " ");
			}
			return;
		}

		for (int i = -10; i <= 10; i++) {

			// 누적 더하기
			for (int j = 0; j <= cnt; j++) { // 열
				for (int k = cnt; k < n; k++) { // 행
					sum[j][k] += i;
				}
			}

			boolean able = true;
			for (int j = 0; j <= cnt; j++) {
				char sign = s[j][cnt];
				int num = sum[j][cnt];
				// 안되는 경우
				if ((sign == '+' && num <= 0) || (sign == '-' && num >= 0) || (sign == '0' && num != 0)) {
					able = false;
					break;
				}
			}

			// 가능한 경우
			if (able)
				go(cnt + 1);

			// 더했던거 빼기
			for (int j = 0; j <= cnt; j++) { // 열
				for (int k = cnt; k < n; k++) { // 행
					sum[j][k] -= i;
				}
			}
		}
	}
}

이 코드의 문제점

반복할 때마다 틀린 경우라도 sum배열의 합들을 전부 바꿔줘서(쓸데없이 반복이 많아짐) 시간이 상당히 오래 걸린다. 

이를 개선하여 해당 부분의 합을 sum이라는 매개변수로 전달해주면 된다.

cnt가 늘어날 때마다 해당 열의 sum들을 검사해주면 되기 때문에, 굳이 배열이 없어도 검사할 수 있다.

추가로 맨 처음 수를 정할 때는 s배열의 첫 번째 부호와만 비교해주면 된다.

따라서, 위의 두 가지 점을 고려하여 코드를 개선하였다.

1. sum배열을 이용하여 모든 수를 비교하지 않고 num 배열을 이용하여 해당 수만 전달하여 해당 열의 수만 비교(배열의 크기도 더 작아서 메모리도 절약된다)
2. 그 숫자가 추가된 열끼리만 sum으로 더해줘서 비교한다(이전의 열들은 이전의 재귀에서 확인했기 때문)

2차 코드

import java.io.*;
import java.util.*;

public class Main {
	private static int n;
	private static boolean success;
	private static char[][] s;
	private static int[] num;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		String string = br.readLine();
		s = new char[n][n];
		num = new int[n];

		// 입력부
		int cnt = -1;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				cnt++;
				s[i][j] = string.charAt(cnt);
			}
		}

		// 함수
		success = false;
		go(0);

	}

	private static void go(int idx) {
		// 한 번 찾으면 끝나야함
		if (success)
			return;

		// 완료조건: 수열이 N개만큼 쌓였을 때
		if (idx >= n) {
			success = true;
			for (int i = 0; i < n; i++) {
				System.out.print(num[i] + " ");
			}
			return;
		}

		findNum: for (int i = -10; i <= 10; i++) {
			num[idx] = i;
			// 열의 수를 비교하는 부분
			int sum = 0;
			boolean check = true;
			for (int j = idx; j >= 0; j--) {
				sum += num[j];

				// 해당 부분 부호 비교, 틀렸을 때 > 숫자를 바꾼다
				if ((s[j][idx] == '+' && sum <= 0) || (s[j][idx] == '-' && sum >= 0)
						|| (s[j][idx] == '0' && sum != 0)) {
					check = false;
					break;
				}
			}
			if (check)
				go(idx + 1);
		}

	}
}

시간이 무진장 줄었다