C++ 코딩테스트 공부 (중단)/c++ 백준 문제풀이

백준 c++ 2447번 별찍기 - 10

2022. 5. 22. 22:50

 

백준 c++ 2447번 별찍기 - 10

 

문제 :

풀이 :

 

 

첫 번째 접근 : 모든 공백을 통해 규칙 살펴보기 ( X )

이렇게 생각없이 접근하지말고 분할해서 생각해보자

이렇게 모든 공백을 가정해보면 규칙이 눈에 들어오지 않는다.

생각을 해야한다.

일반화된 규칙을 찾아 재귀함수를 이용해 별을 찍을 수 있지 않을까

 

 

두 번째 접근 : 재귀함수를 이용해 분할해서 생각하기

(i, j, n)을 재귀함수가 받아 처리한다고 생각해보자

재귀함수를 이용해서 9 x 9 (n=9)일 때 i,j 좌표가 중앙일 때 공백을 출력한다.

그 다음 3 x 3 (n=3)일 때 i,j 좌표가 중앙일 때 공백을 출력한다.

n이 1이 되면 중단한다.

 

이렇게 n을 3으로 나누며 실행하는 재귀함수를 통해 원하는 별찍기 결과를 얻을 수 있다.

그런데 규칙은 어떻게 작성해야할까?

9x9 일 때(n=9), 중앙 공백 좌표는 3, 4, 5이다. 즉, (i/3) % 3이 1일 때이다.

따라서 9x9 크기에서 중앙 공백 좌표는 (i/3) % 3 == 1 && (j/3) % 3 == 1 로 표현할 수 있다.

3x3일 때는(n=3), 중앙 공백 좌표는 1, 4, 7이다. 즉, i % 3이 1일 때 이다.

따라서 3x3 크기에서 중앙 공백 좌표는 i % 3 == 1 && j % 3 == 1 로 표현할 수 있다.

재귀함수를 생각해 일반화된 규칙을 만들어야 하므로

(i/1) % 3 == 1 &&(j/1) % 3 == 1 의 규칙을 가진다고 표현할 수 있다.

 

이제 재귀함수를 통해 n이 3으로 나누어지면서 해당 규칙들을 만족시키게 작성해보면

크기 n에서 재귀함수를 통해 중앙 공백 좌표 규칙은 

(i/(n/3)) % 3 == 1 && (j/(n/3)) % 3 == 1

이렇게 작성할 수 있다.

이렇게 되면 n이 9일 때, (i/3)

n이 3일 때, (i/1) 규칙을 만족시킨다. n이 그보다 높은 수일 때도 마찬가지이다.

일반화된 규칙을 찾은 것이다.

 

#include<iostream>

using namespace std;

void recur(int i, int j, int x) {
    if (x == 1) {
        cout << "*";
        return;
    }
    else if ((i/(x/3)) % 3 == 1 && (j/(x/3)) % 3 == 1) {
        cout << " ";
    }
    else {
        recur(i, j, (x/3));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            recur(i, j, n);
        }
        cout << "\n";
    }

    return 0;
}

 

 

'C++ 코딩테스트 공부 (중단) > c++ 백준 문제풀이' 카테고리의 다른 글

백준 c++ 17478번 문제 : 재귀함수가 뭔가요?  (0) 2022.05.21
#8 기본수학2 - 2  (0) 2022.04.06
#8 기본 수학2 - 1  (0) 2022.04.05
#7 기본 수학1 - 2  (0) 2022.04.04
#7 기본 수학1 - 1  (0) 2022.04.01
'C++ 코딩테스트 공부 (중단)/c++ 백준 문제풀이' 카테고리의 다른 글
  • 백준 c++ 17478번 문제 : 재귀함수가 뭔가요?
  • #8 기본수학2 - 2
  • #8 기본 수학2 - 1
  • #7 기본 수학1 - 2
daramG
daramG
dotori Java
daramG
다람쥐의 개발 블로그
daramG
전체
오늘
어제
  • 분류 전체보기 (193)
    • Java 코딩테스트 공부 (67)
      • Java 알고리즘 공부 (37)
      • Java 백준 문제풀이 (27)
      • Java 코테 나만의 팁 (3)
    • SQL Study (0)
      • Programmers SQL 문제풀이 (0)
      • SQLP 준비 (0)
    • 웹 개발 지식 정리 (0)
      • Servlet (0)
      • Java 정리 (0)
    • 자바 스프링 (45)
      • 스프링 공부 (4)
      • 스프링 게시판 프로젝트 (6)
      • 부트 블로그 JPA 프로젝트 (30)
      • react & springboot (5)
      • 스프링 오류창고 (0)
      • 리액트 + 스프링 프로젝트 (0)
      • pf (0)
      • pfError (0)
    • React (6)
      • React 정리 (3)
      • React 오류 창고 (3)
    • C++ 코딩테스트 공부 (중단) (20)
      • c++ 백준 문제풀이 (15)
      • c++ 알고리즘 공부 (5)
    • Unity (3)
      • Unity 공부 (3)
    • WebRTC (2)
      • WebRTC 강의학습 정리 (0)
      • WebRTC 프로젝트 (1)
    • 김영한님의 스프링 강의 학습 (10)
      • 스프링 강의 목차 (1)
      • 인텔리제이 & 스프링 기초 (1)
      • 스프링 핵심 원리 (8)
    • 전공 지식 정리 (40)
      • interview (0)
      • Java (0)
      • 운영체제 (4)
      • 데이터베이스 설계 (10)
      • 소프트웨어 공학 (3)
      • 유닉스 (14)
      • 디지털 논리회로 (0)
      • 인공지능 (7)
      • js (0)
      • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Java 백준 문제풀이
  • 스프링부트 프로젝트
  • 노마드코더의 zoom클론코딩
  • 무서운 이야기
  • 김영한 스프링 강의
  • Unity 공부
  • 데이터베이스 설계
  • 디지털 논리회로
  • java
  • 부트 jpa 게시판 프로젝트
  • 김영한 스프링 입문
  • 스프링 공부
  • 운영체제
  • 스프링 프로젝트
  • Java 코테 나만의 팁
  • C++ 알고리즘
  • 인공지능
  • React&Spring 강의수강
  • 김영한의 스프링 핵심 원리
  • java 알고리즘
  • 백준 c++
  • 스프링부트 블로그 프로젝트
  • 유닉스
  • 코테 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.
daramG
백준 c++ 2447번 별찍기 - 10
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.