- 백준 :: #2447 별찍기 - 10 [Gold V][Java]2023년 09월 12일
- 엘티티
- 작성자
- 2023.09.12.:43
* 문제
https://www.acmicpc.net/problem/2447
* 풀이 과정
우선 모양들이 일정한 규칙을 이루고 있는것부터 주목을 해야된다.
파란색 네모쳐 놓은 것이 기본 틀이되는 3x3 형태의 가운데가 비어있는 모양이고, 붉은색 네모쳐 놓은 것이 기본틀을 3x3형태로 가운데가 비어있는 모양, 그리고 전체가 붉은색 네모쳐 놓은 모양을 3x3 형태로 배열하고 가운데를 비워놓은 모양이다.
문제에서 입력받는 값을 모양의 한 변(?)의 최대 길이, max라는 변수로 지정해보자면,
max = 3 -> 파란색 / max = 9 -> 붉은색 / max = 27 -> 위 그림의 전체
라고 생각할 수 있게 된다.그래서 나는 재귀함수를 이용하여, 재귀함수 안에서 max = 3인 도형부터 이용하여 각 단계별로 모양을 만들고, 다음 단계에 그 도형을 매개변수로 보내어, 만든 도형들을 계속해서 활용할 생각을 했다.
없어보이지만 소박한 조건을 정리해보자면,- 첫 단계를 제외한 모양은 이전 단계의 모양을 3x3으로 배열한 모양이다.
- 이전 단계의 모양을 채워야되는 가운데 부분은 빈칸으로 한다.이 두가지만 지키면, 문제없이 재귀를 사용하여 만들 수 있겠다는 생각을 하였고, 다음은 내가 java로 구현한 코드이다.
* 코드
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.BufferedWriter; public class j2447 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); char[][] square = {{'*','*','*'},{'*',' ', '*'},{'*','*','*'}}; int max = Integer.parseInt(br.readLine()); char[][] shape = build(square, 3, max); for(int i = 0; i < shape.length; i++) { bw.write(shape[i]); bw.write("\n"); } bw.flush(); bw.close(); } public static char[][] build(char[][] square, int n, int max) { if (max == 3) return square; char[][] shape = new char[n*3][n*3]; // 세로 for(int i = 0; i < shape.length; i++) { // 가로 for(int j = 0; j < shape[i].length; j++) { if(i >= n && i < n*2 && j >= n && j < n*2) shape[i][j] = ' '; else shape[i][j] = square[i%n][j%n]; } } if(n*3 < max) { shape = build(shape, n*3, max); } return shape; } }
* 코드 설명
main 변수
- br, bw : br은 입력을 받기위한 BufferedReader, bw는 출력을 하기위한 BufferedWriter이다. (이 문제같은 경우에는 System.out.println()으로 출력하게 되면 호출시간이 너무 길어져 '시간 초과'로 틀린다.)(이미 틀려보고 한참 헤맸다)
- char[][] square : 가장 기본이 되는 모양을 2차원 배열로 저장한 변수
- int max : 입력값으로, 최종적으로 만들어야 될 모양의 가로와 세로(변) 길이
- char[][] shape : 최종적으로 출력하게 되는 모양을 2차원 배열로 저장할 변수build 변수
- char[][] square, int n, int max : square는 이전단계의 모양 배열, n은 이전 단계의 모양의 변의 길이, max는 최종적으로 구하고자 하는 모양의 변의 길이
- char[][] shape : 반환하고자 하는 최종적인 정답이 되는 모양의 배열, 각 단계에서 (이전 모양의 길이) * 3을 하여 선언하고 저장함
=> 핵심 메소드로, 내부에서 반복문을 이중으로 사용하여 기존모양을 이용하여 새로운 모양에 저장하는 방식을 이용함.
가운데 조건문에서는 가운데 비어있어야 되는 부분인지 판별함.
P.S. 설명 거지같이 써서, 문제나 문의사항 있을 시에 연락주세요.'백준_코딩테스트 > Divide_and_Conquer' 카테고리의 다른 글
백준 :: #1891 사분면 [Gold IV][Python] (0) 2023.09.22 백준 :: #18222 투에-모스 문자열 [Silver II][Python] (0) 2023.09.20 백준 :: #1074 Z [Silver I][Java] (0) 2023.09.13 다음글이전글이전 글이 없습니다.댓글