이 영역을 누르면 첫 페이지로 이동
시간의화살 블로그의 첫 페이지로 이동

시간의화살

페이지 맨 위로 올라가기

시간의화살

행복하세요

[백준] 17136 색종이 붙이기 - Java

  • 2022.08.17 19:18
  • Algorithm/Baekjoon

 

 

 

붙이는 개수가 최소가 돼야 한다.

크기가 큰 색종이부터 쓰면 최소 개수를 구할 수 있다.

 

스도쿠 문제를 풀 때 처럼 좌측 상단에서 우측 하단으로 내려가면서 탐색한다.

 

색종이로 덮는 작업과 덮은걸 치우는 작업은 따로 메서드로 만들어서 진행하자.

 

사용할 수 있는 색종이의 수가 정해짐에 유의하고 백트래킹을 돌리면 된다.

 

 

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

public class Main {
    static int[][] map = new int[10][10];
    static int ans = Integer.MAX_VALUE;
    static int[] remain = {0, 5, 5, 5, 5, 5};

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));     

        for(int i=0; i<10; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<10; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bt(0,0,0);

        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);        

        
       

    }

    static void bt(int r, int c, int cnt){
        if(r == 10){
            ans = Math.min(ans, cnt);            
            return;
        }
        
        if(c == 10){
            bt(r + 1, 0, cnt);
            return;
        }
        

        if(cnt >= ans){
            return;
        }

        if(map[r][c] == 1){
            for(int i = 5; i >= 1; i--){
                if(isCover(r, c, i) && remain[i] > 0){
                    cover(r, c, i);
                    remain[i]--;
                    bt(r, c + 1, cnt + 1);
                    undo(r, c, i);
                    remain[i]++;
                }
            }
        }else if (map[r][c] == 0 || map[r][c] == -1){
            bt(r, c + 1, cnt);
        }
        

    }

    static boolean isCover(int r, int c, int size){
        for(int i = r; i< r + size; i++){
            for(int j = c; j < c + size; j++){
                if(i >= 10 || j >= 10){
                    return false;
                }

                if(map[i][j] != 1){
                    return false;
                }
            }
        }

        return true;
    }

    static void cover(int r, int c, int size){
        for(int i=r; i< r + size; i++){
            for(int j=c; j<c + size; j++){
                map[i][j] = -1;
            }
        }
    }

    static void undo(int r, int c, int size){
        for(int i=r; i<r + size; i++){
            for(int j=c; j<c + size; j++){
                map[i][j] = 1;
            }
        }
    }
}
반응형
저작자표시 (새창열림)

'Algorithm > Baekjoon' 카테고리의 다른 글

[백준] 1553 도미노 찾기 - Java  (0) 2022.08.18
[백준] 15658 연산자 끼워넣기 (2) - Java  (0) 2022.08.18
[백준] 6443 애너그램 - Java  (0) 2022.08.17
[백준] 3980 선발 명단 - Java  (0) 2022.08.17
[백준] 1325 효율적인 해킹 - Java  (0) 2022.08.14

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 1553 도미노 찾기 - Java

    [백준] 1553 도미노 찾기 - Java

    2022.08.18
  • [백준] 15658 연산자 끼워넣기 (2) - Java

    [백준] 15658 연산자 끼워넣기 (2) - Java

    2022.08.18
  • [백준] 6443 애너그램 - Java

    [백준] 6443 애너그램 - Java

    2022.08.17
  • [백준] 3980 선발 명단 - Java

    [백준] 3980 선발 명단 - Java

    2022.08.17
다른 글 더 둘러보기

정보

시간의화살 블로그의 첫 페이지로 이동

시간의화살

  • 시간의화살의 첫 페이지로 이동

검색

방문자

  • 전체 방문자
  • 오늘
  • 어제

카테고리

  • 분류 전체보기 (607)
    • Algorithm (205)
      • Data Structure (5)
      • Theory && Tip (33)
      • Baekjoon (166)
      • ALGOSPOT (1)
    • Spring (123)
      • Spring (28)
      • Spring Web MVC (20)
      • Spring Database (14)
      • Spring Boot (6)
      • Spring 3.1 (11)
      • Spring Batch (6)
      • Spring Security (16)
      • JPA (12)
      • Spring Data JPA (5)
      • QueryDSL (4)
      • eGovFramework (1)
    • Programming Language (74)
      • Java (19)
      • JavaScript (15)
      • C (25)
      • C++ (12)
      • Python (1)
      • PHP (2)
    • Computer Science (69)
      • Operating System (18)
      • Computer Network (17)
      • System Programming (22)
      • Universial Programming Lang.. (8)
      • Computer Architecture (4)
    • Database (21)
      • Database (7)
      • MySQL (3)
      • Oracle (3)
      • Redis (5)
      • Elasticsearch (3)
    • DevOps (20)
      • Docker && Kubernetes (8)
      • Jenkins (4)
      • Github Actions (0)
      • Amazon Web Service (8)
    • Machine Learning (28)
      • AI Introduction (28)
    • Mobile (28)
      • Android (21)
      • Flutter (7)
    • Solutions (14)
    • Life Logs (0)
    • 낙서장 (25)

최근 글

나의 외부 링크

메뉴

  • 홈

정보

13months의 시간의화살

시간의화살

13months

블로그 구독하기

  • 구독하기
  • RSS 피드

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © 13months.

티스토리툴바