[백준, Java] 12979번, 종이 접기(정수론)

문제 링크

12979번: 종이 접기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. W × H 크기의 종이가 주어집니다.

2. 종이를 접는 조건은 문제에 내용과 같습니다.

3. 종이를 접어서 넓이 A을 만들 때 최소 접는 횟수를 결과로 출력합니다.

4. 넓이 A로 만들 수 없다면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 넓이 A의 약수를 기준으로 완전탐색을 통해 종이를 접어봅니다.

 

3. 모두 접어본 뒤 최소 접은 횟수를 결과로 출력합니다.

 

 

종이 접기

 

종이를 접는 경우는 크게 2개로 볼 수 있습니다.

 

1. 현재 길이(W or H) ÷ 2   ≤  만들어야 하는 길이 ≤ 현재 길이(W or H)

 

→ 반으로 접거나 해당 길이가 되도록 접습니다.

 

→ 접는 과정을 종료합니다.(해당 길이로 변경 완료!)

 

※ 만약 현재 길이가 홀수이면 +1을 진행해야 합니다.

▶ 이유는 간단한 종이를 반으로 접으면 큰 쪽이 남기 때문에 +1을 해주어야 합니다.

 

2. 만들어야 하는 길이  >  현재 길이(W or H) ÷ 2

 

→ 반으로 접습니다.

 

→ 접는 과정을 반복합니다.(해당 길이로 변경하도록 계속 접기!)

 

※ 반으로 접는 것은 길이를 최대한 줄이는 방법입니다.

 

넓이 A 의 약수 구한 뒤 종이 접어보기

 

넓이 A에 1부터 순차적으로 나누어 떨어지는 값에 대한 약수들을 탐색합니다.

 

for (int i = 1; i <= Math.sqrt(A); i++) {
      if (A % i == 0) {
          measures.add(i);
          measures.add(A / i);
     }
}

 

접어서 만들어야 하는 길이가 W, H보다 크다면 해당 길이는 만들 수 없기 때문에 넘깁니다.

 

//measure : 약수
int val = A / measure;
if(measure > W || val > H){
      continue;
}

 

 

이후, 위에서 설명한 대로 종이를 접는 횟수를 구한 뒤 최소 접는 횟수를 탐색합니다.

 

※ 예제입력을 확인하시면 이해하시기 편하실 것입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

W : 5

 

H : 3

 

A : 12

 

2. 넓이 A의 약수를 기준으로 완전탐색을 통해 종이를 접어봅니다.

 

약수 구하기

 

 

12 : { 1, 2, 3, 4, 6, 12}

 

 

 

종이 접기 진행

 

W : 1, H : 12

 

→ H는 12을 만들 수 없기 때문에 넘깁니다.

 

 

W : 2, H : 6

 

→ H는 6을 만들 수 없기 때문에 넘깁니다.

 

 

W : 3, H : 4

 

→ H는 4을 만들 수 없기 때문에 넘깁니다.

 

 

W : 4, H : 3

 

W을 4으로 만드는 과정

 

현재 길이(W or H) ÷ 2   ≤  만들어야 하는 길이 ≤ 현재 길이(W or H) 성립

 

3 ≤ 4 ≤ 5

 

1번만 접으면 해당 길이를 만들 수 있습니다.

 

H을 3으로 만드는 과정

 

→ H는 이미 3이기 때문에 접지 않아도 됩니다.

 

▶ 1(W접은 횟수) + 0(H접은 횟수) = 1번

 

 

W : 6, H : 2

 

→ W는 6을 만들 수 없기 때문에 넘깁니다.

 

 

W : 12, H : 1

 

→ W는 12을 만들 수 없기 때문에 넘깁니다.

 

3. 모두 접어본 뒤 최소 접은 횟수를 결과로 출력합니다.

 

W : 4, H : 3 → 최소 접는 횟수 : 1번

 

1을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 W, H, A의 정보를 띄어쓰기 기준 나누었습니다.
• W × H가 넓이 A보다 작으면 해당 넓이를 만들 수 없으므로 -1을 BufferedWriter 저장합니다.
• 넓이 A에 대한 약수를 구합니다.
• 약수를 구한 뒤 foldPaper함수를 통해 종이 접기를 진행하여 최소 접는 횟수를 탐색합니다.
• 최소 종이 접는 횟수를 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• foldPaper함수는 종이를 접는 과정을 진행합니다.

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //입력값 저장
        long W = Long.parseLong(st.nextToken());
        long H = Long.parseLong(st.nextToken());
        int A = Integer.parseInt(st.nextToken());
        //기본값 설정(넓이 A를 만들 수 없을 때)
        int result = -1;
        //넓이 A를 만들 수 있을 때
        if(A <= W*H) {
            result = Integer.MAX_VALUE;
            List<Integer> measures = new ArrayList<>();
            //약수 구하기
            for (int i = 1; i <= Math.sqrt(A); i++) {
                if (A % i == 0) {
                    measures.add(i);
                    measures.add(A / i);
                }
            }
            //종이 접기 진행
            for (int measure : measures) {
                int val = A / measure;
                //W나 H을 해당 길이로 만들 수 없을 때
                if(measure > W || val > H){
                    continue;
                }
                //접는 횟수 구하기
                int cnt = foldPaper(W, measure) + foldPaper(H, val);
                //최소 접는 횟수 비교
                result = Math.min(result, cnt);
            }
            //해당 넓이로 접을 수 없을 때
            if(result == Integer.MAX_VALUE)
                result = -1;
        }
        //최소 접는 횟수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //종이 접는 2가지 경우를 기준으로 접기 진행
    public static int foldPaper(long len, int goal){
        int cnt = 0;
        while(len > goal){
            //현재 길이가 홀수일 때
            if(len % 2 == 1){
                len++;
            }
            len /= 2;		//접기 진행
            cnt++;	//접기 횟수 증가
        }
        return cnt;
    }
}