| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 |
- 다이나믹 프로그래밍
- KMP알고리즘
- 연결리스트 중복제거
- 구현
- 연결리스트 정렬
- 스택
- 브루트포스 알고리즘
- 해시를 사용한 집합과 맵
- LeetCode 83번
- 재귀
- LeetCode 83 c언어
- 별 찍기
- 조합론
- Queue
- 문자열제곱
- LeetCode Remove Duplicates from Sorted List in c
- 큰 수 연산
- 프로그래머스
- 큐
- 임의 정밀도 / 큰 수 연산
- 문자열
- 사칙연산
- 정수론
- 시뮬레이션
- 실패함수
- 수학
- 정렬
- 이분 탐색
- 자료 구조
- 유클리드 호제법
- Today
- Total
hahn
단계별로 풀어보기(재귀 - 별 찍기 - 10) 본문
2447번: 별 찍기 - 10 (acmicpc.net)
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
6시간째 고민 중...
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int insertNumber = (int) Math.pow(Integer.parseInt(br.readLine()), 2);
int notInsert, count = 0, var = 0;
String[] str = new String[insertNumber];
for(int i = 0; i < 9; i++) {
if(i == 4) {
str[i] = " ";
}else {
str[i] = "*";
}
}
for(int i = 1; Math.pow(9, i + 1) <= insertNumber; i++) {
for(int j = (int) Math.pow(9, i); j < Math.pow(9, i + 1); j++) {
notInsert = (int) (Math.pow(9, i + 1) / Math.pow(9, 1)) * 4;
if(notInsert <= j && notInsert + Math.pow(9, i) > j) {
str[j] = " ";
}else {
str[j] = str[j % (int) Math.pow(9, i)];
}
}
}
for(int i = 0; i < Math.sqrt(insertNumber); i++) {
for(int j = 0; j < Math.sqrt(insertNumber)/3; j++) {
if(j != 0)count += (int)(Math.sqrt(insertNumber));
for(int k = 0; k < 3; k++) {
System.out.println(k + count);
bw.write(str[(k + count)]);
var++;
}
}
System.out.println(var + "var");
System.out.println(count + "count");
System.out.println(var / (int)(Math.sqrt(insertNumber)) % (int)(Math.sqrt(insertNumber)) + "vari");
if(var / ((int)(Math.sqrt(insertNumber))/3) % (int)(Math.sqrt(insertNumber))/3 != 0)count -= (int)(Math.sqrt(insertNumber) * 2) - 3;
if(var > ((int)(Math.sqrt(insertNumber))/3)) if(var / ((int)(Math.sqrt(insertNumber))/3) % (int)(Math.sqrt(insertNumber))/3 == 0) count += (int)(Math.sqrt(insertNumber)/3);
System.out.println(count + "countafter");
bw.newLine();
}
bw.close();
}중간 결과물이다.
생각을 엄청나게 많이 했다.
2차원 배열로 풀어볼까부터 해서
거의 2시간가량 생각했는데
최종적으로 채택된 아이디어는
3 * 3을 만들 때 5번 부분이 비니까
이를 좀 더 확장해서 생각하면 전체를 9등분 했을 때 5번째 부분이
비는 거니까 이를 이용해서
String[] str = new String[insertNumber];
for(int i = 0; i < 9; i++) {
if(i == 4) {
str[i] = " ";
}else {
str[i] = "*";
}
}
for(int i = 1; Math.pow(9, i + 1) <= insertNumber; i++) {
for(int j = (int) Math.pow(9, i); j < Math.pow(9, i + 1); j++) {
notInsert = (int) (Math.pow(9, i + 1) / Math.pow(9, 1)) * 4;
if(notInsert <= j && notInsert + Math.pow(9, i) > j) {
str[j] = " ";
}else {
str[j] = str[j % (int) Math.pow(9, i)];
}
}
}이렇게 넣었다 이제 출력 부분만 해결하면 되는데
여기만 3시간째 고민 중인데 안 된다.
/는 개행이다
3 * 3일 때는 012/ 345/ 678를
9 * 9일 때는
**** ******** ******** ******** **** **** ******** ******** ******** ****
0 1 2 9 10 11 18 19 20 / 3 4 5 12 13 14 21 22 23 / 6 7 8 15 16 17 24 25 26
27.. 생략
-- 여기부터는 정확하지 않은데 내 머릿속으로는 이렇다 --
27 * 27일 때는
**** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** **** **** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** ******** ******** ******** ******** **** **** ******** ******** ******** ****
0 1 2 27 28 29 54 55 56 9 10 11 36 37 38 63 64 65 18 19 20 45 46 47 71 72 73
/
3.. /
6.. /
81../
이걸 출력 부분에 표현하면 되는 거 같은데 도저히 못 하겠다.
될 거 같으면서도 안 되는 게 매우 답답하다.
변수 잡는 것부터해서 후.. 답이 없다.
15:00
+ 그냥 어차피 똑같은 패턴 4번 반복 공백 4번 반복이니까 그걸 기준으로 잡을까
+근데 어차피 규모가 커지면 똑같은 로직임
19:00
밥 먹고 왔는데 그냥 공백을 수식화할까
23:00
너무 길어서 개행 없앴다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine(),
blank;
double insertNumber = Double.parseDouble(str),
totalCount = Math.pow(insertNumber, 2);
int breakCount = 9, pow = 3;
String[] strArr
,printArr = new String[3];
for(int i = 0; i < 9; i++) {
if(printArr[i % 3] == null) printArr[i % 3] = "";
if(i != 4) {
printArr[i % 3] += "*";
}else {
printArr[i % 3] += " ";
}
}
while(breakCount < insertNumber * 3) {
strArr = printArr;
printArr = new String[breakCount];
blank = "";
for(int i = 0; i < breakCount / 3; i++) {
blank += " ";
}
for(int i = 0; i < printArr.length; i++) {
if(printArr[i] == null) printArr[i] = "";
for(int j = 0; j < 3; j++) {
if((i >= printArr.length / 3 && i < (printArr.length / 3 * 2)) && j == 1) {
printArr[i] += blank;
}else {
printArr[i] += strArr[i % strArr.length];
}
}
}
breakCount = (int) Math.pow(3, pow++);
}
for(int i = 0; i < printArr.length; i++) {
bw.write(printArr[i]);
bw.newLine();
}
bw.close();
}
}
드디어 해결했다.
완전 처음에 잠깐 스쳐지나갔었던 생각이 정답이었다.
이 문제는 주제는 재귀인데 이걸 그냥 지나친 게 잘못이다.
생각하다가 내가 놓치고 있는 부분이 있을까 하고
액셀에 인덱스 번호를 전부 찍어봤다.
빨간색 부분이 공백 부분인데
도저히 봐도 전부를 수식화하기는 힘들겠다고 생각했다.
근데 이게 아주 쓸모없는 일은 아니었다.
252 ~ 260... 476과 84 ~ 86... 140 그리고 28의 인덱스를
계산해봤는데 얘네는 구할 수 있어도 나머지는 해결을 못하겠다고 생각하던 중
얘네를 이용해서 string을 += 해서 별을 찍으면 되겠는데? 하고 생각이 들었다.
for(int i = 0; i < 9; i++) {
if(printArr[i % 3] == null) printArr[i % 3] = "";
if(i != 4) {
printArr[i % 3] += "*";
}else {
printArr[i % 3] += " ";
}
}일단 초기 형태 잡아주고
입력 값의 3의 지수만큼 반복해야 하니
while문 열어주고
조건은 고민하다가 대충 때려 박았다
while(breakCount < insertNumber * 3)
breakCount 초기 값은 9로 3 들어오면 실행 안 되게 했다.
breakCount = (int) Math.pow(3, pow++);
pow는 3으로 시작.
while(breakCount < insertNumber * 3) {
strArr = printArr;
printArr = new String[breakCount];
blank = "";
for(int i = 0; i < breakCount / 3; i++) {
blank += " ";
}
for(int i = 0; i < printArr.length; i++) {
if(printArr[i] == null) printArr[i] = "";
for(int j = 0; j < 3; j++) {
if((i >= printArr.length / 3 && i < (printArr.length / 3 * 2)) && j == 1) {
printArr[i] += blank;
}else {
printArr[i] += strArr[i % strArr.length];
}
}
}
breakCount = (int) Math.pow(3, pow++);
}
안쪽은 이렇게 채워줬는데
그냥 간단하게 말하면
이전 형태를 저장해주려고
배열 두 개 선언했고,
배열을 저장 후에는
새 배열을 출력되어야 하는 줄 수만큼 크기를 할당해줬다.
(배열 초기화)
이후
이렇게 세로로 3 등분하면
첫 번째와 마지막은 원형을 3번 반복해주면 된다.
하지만 2번째가 문제인데
얘를 또 3 등분하고 2번째는 공백을 넣어줘야 한다.
그래서 공백 변수를 하나 만들었고,
얘는 새로 생성되는 배열의 줄 수의 1 / 3 이면 된다.
(n*n의 배열이기 때문에)
암튼 이렇게 하니까 완성됐다.
결론만 말하면 이전에 생성된 배열의 한 줄이 3번 반복하면 한 줄임.
공백 부분만 판단해주면 됨
어제오늘 거의 10시간가량 코드 짜 보고
자는 시간, 밥 먹는 시간 이것만 머리에 맴돌았는데
방향을 새로 잡으니 1시간도 안 걸려서 끝나버렸다.
지금 보니 그렇게 어려운 문제가 아니었는데
출제 의도를 벗어나서 그랬던 거 같다.
그래도 즐거운 시간이었다!
'코딩테스트 연습 > 백준(JAVA)' 카테고리의 다른 글
| 단계별로 풀어보기(브루트 포스 - 블랙잭) (0) | 2021.08.31 |
|---|---|
| 단계별로 풀어보기(재귀 - 하노이 탑 이동 순서) (0) | 2021.08.30 |
| 단계별로 풀어보기(재귀 - 피보나치 수 5) (0) | 2021.08.25 |
| 단계별로 풀어보기(재귀 - 팩토리얼) (0) | 2021.08.25 |
| 단계별로 풀어보기(기본 수학2 - 터렛) (0) | 2021.08.24 |
