[1074] Z (C++17)

2025. 2. 6. 10:36·백준

문제

 

풀이

아래 그림처럼 생각해서 재귀로 풀면 된다.

n=3, r=7, c=7인 경우의 그림이다. (빨간 체크가 내가 가야 하는 곳)

재귀 함수를 z(int n, int r, int c)라고 가정,

재귀가 돌아가는 과정을 식으로 나타내면 아래와 같다.

 

z(3, 7, 7)

= 3*4*4 + z(2, 3, 3)

= 48 + (3*2*2 + z(1, 1, 1))

= 48 + (12 + (3*1*1 + z(0, 0, 0)))

= 48 + 12 + 3

= 63

 

답안

#include <iostream>

using namespace std;

int z(int n, int r, int c) {
    if (n == 0) {
        return 0;
    }
    int half = 1 << (n-1); // 2의 n-1승

    if (r < half && c < half) {
        return z(n-1, r, c);
    }

    if (r < half && c >= half) {
        return half*half + z(n-1, r, c-half);
    }

    if (r >= half && c < half) {
        return 2*half*half + z(n-1, r-half, c);
    }

    return 3*half*half + z(n-1, r-half, c-half);
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, r, c;

    cin >> n >> r >> c;

    cout << z(n, r, c) << '\n';
}

 

'백준' 카테고리의 다른 글

[9251] LCS (C++17)  (1) 2025.03.23
[1463] 1로 만들기 (C++17)  (0) 2025.03.23
[2493] 탑 (C++17)  (0) 2025.01.20
[17298] 오큰수 (C++17)  (0) 2025.01.20
[3015] 오아시스 재결합 (C++17)  (0) 2025.01.20
'백준' 카테고리의 다른 글
  • [9251] LCS (C++17)
  • [1463] 1로 만들기 (C++17)
  • [2493] 탑 (C++17)
  • [17298] 오큰수 (C++17)
gmlwlsl
gmlwlsl
https://github.com/gmlwlsdl
  • gmlwlsl
    프론트엔드 개발 관련 지식 정리 및 회고록 모음집 입니다. (シ. .)シ
    gmlwlsl
  • 전체
    오늘
    어제
    • 분류 전체보기 (41) N
      • 백준 (15)
      • Visualizer (10)
      • 구름톤 유니브 (1)
      • FE (10) N
      • BE (1)
      • 카카오 클라우드 네이티브 in 제주 (4)
      • 디프만 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    9oormthonuniv
    백준 #23971
    구름톤 유니브 3기
    vite
    3015
    30504
    카카오테크 부트캠프 클라우드 in 제주
    aws #kubernetes
    C++
    백준
    fe
    백준 #2292
    11003
    Toss Fundamentals
    JS
    aws #docker
    aws #docker #tomcat
    17298
    백준 #7568
    백준 #9655
    kubernetes #k8s
    ErrorBoundary
    frontend
    aws #docker #mysql #heidisql
    백준 #5073
    2493
    어우힘들어
    react
    백준 #1157
    Web
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
gmlwlsl
[1074] Z (C++17)
상단으로

티스토리툴바