문제 탐색하기

입력 자료 정리

1. H는 모눈종이의 높이, W는 모눈종이의 너비다
2. N은 스티커의 개수, R은 주어진 각 스티커의 높이, C는 스티커의 너비다

해결방법 추론

1. 해당 문제는 스티커를 두개만 골라서 모눈종이를 덮는 경우를 구하고,
   그중 가장 큰 넓이를 정답으로 출력하는 문제다
2. 제일먼저 떠올릴 수 있는 방법은 브루트포스다.
   스티커를 두개만 고르면 되기 때문에 모눈종이의 높이나 너비를 벗어나지 않는지 확인하고,
   벗어나지 않는다면 max값에 두 스티커의 넓이와 비교하여
   더 큰 값을 넣는 방식으로 해결하면 된다
3. 하지만 브루트포스 방식은 시간제한에 걸릴 수 있다는 위험성이 있다.
   따라서 시간복잡도를 계산해야한다

시간복잡도 계산

1. 두 스티커를 비교하기 위해서는 스티커의 개수 n만큼 반복문을 돌면된다
2. 이때, '두' 스티커이므로 이중포문으로 반복문을 돌린다
3. 다른 어떤 경우도 이 시간복잡도보다 최악의 경우는 나올 수 없다
4. 따라서 시간복잡도는 O(n^2)이 된다
5. n의 최대 입력값은 100이다. 100*100 = 10,000이므로 시간제한에 걸리지 않는다
6. 따라서 브루트포스로 해당문제를 해결할 수 있다!

코드 설계하기

스티커 상태 관리하기

1. R과 C를 관리하기 위해 클래스를 Pair 클래스를 하나만들었다.
2. 그리고 Pair타입의 리스트를 만들어서 해당 R과 C를 필드로 하는 인스턴스를 추가한다
3. 배열도 선택지가 될 수 있지만, 일부 입력값중 추가되지 않는 경우가 있기 때문에
   전체 크기가 확정되지 않아 배열을 포기하고 리스트를 선택하였다

입력 로직 설계

1. 언제나 그랬듯이 BufferedReader와 StringTokenizer를 사용하여 입력값을 받는다
2. h,w,n은 int 변수로 받아주고, n만큼 순회를 돌면서 r과 c도 입력받는다
3. r과 c가 h와 w보다 크다면 해당 스티커는 선택되어도 모눈종이를 덮을 수 없으로,
   r이 h보다 작거나 같고 c가 w보다 작거나 같을 때만 리스트에 Pair 객체를 만들어서 넣어준다
4. 문제의 조건이 하나 더 있다. 스티커를 90도로 돌릴 수 있다는 조건이다
5. 해당 조건을 이후 탐색과정에서 복잡하게 하고 싶지 않아 그냥 원래 경우와 90도로 돌린경우 모두 리스트에 넣었다.
6. 넣는 과정은 r과 c를 바꿔서 비교하고 바꿔서 넣어주면 된다

탐색 로직 설계

1. 정답이 될 max 변수를 하나 만들어준다. 0으로 초기화한다
2. Pair리스트의 크기인 pairs.size()만큼 이중포문을 돌아준다
3. 이때 스티커를 중복해서 선택하는 경우는 제외해야하므로 j의 초기값은 i+1로한다
4. 비교를 위해 i의 r과 j의 r을 더한 height, i의 c와 j의 c를 더한 width를 선언한다
5. 두 스티커의 높이 합이 height보다 크고 width보다도 크다면 모눈종이의 범위를 벗어나므로 continue해서 max와의 비교를 피한다
6. 이어서 max에 Math.max를 사용하며, i와 j의 넓이 합과 비교하고 더 큰값을 넣어준다
7. 완성한 max를 출력하면 정답이 될 것이다
8. 또한 max를 0으로 초기화했기 때문에 스티커가 선택되지 않아도 0을 출력하라는 조건을 만족하게 된다.

시도 회차 수정사항

1회차

• 위 로직으로 첫 제출을 했을 때 27%에서 틀렸다...
• 원인을 분석해보자

원인 분석

1. 어디서 틀렸을까 생각해보니 90도로 돌린 것을 리스트에 같이 넣은 부분에서 중복 선택이 발생할 수 있음을 발견하게 되었다.
2. 즉, 탐색 로직에서 같은 스티커를 원래것과 90도로 돌린 것을 선택하여, 하나의 스티커로 두번 선택하는 중복 선택의 오류가 있음을 알게 되었다

해결 방법

1. 이러한 중복 선택을 방지하기 위해 Pair에 num이라는 필드를 하나 추가하였다
2. 입력받을 때, i를 num에 넣어주어, 90도로 돌린 스티커를 넣어도 같은 스티커라는 구분을 할 수 있게 되었다
3. 이후 탐색 과정에서 모눈종이의 넓이를 벗어나는지 체크하는 구간에 or 비교로 i와 j의 num이 같은지를 비교한다
4. or 비교를 선택한 이유는 and 비교를 하면 num이 다르기만 하면 모눈종이의 범위를 벗어나도 선택할 수 있기 때문이다
5. 같다면 똑같이 continue를 하면된다

정답코드

1회차 (27% 틀린코드)

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


class Pair{

    int r;
    int c;

    public Pair(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(br.readLine());

        List<Pair> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(r <= h && c <= w){
                pairs.add(new Pair(r, c));
            }

            if(c <= h && r <= w){
                pairs.add(new Pair(c, r));
            }
        }

        int max = 0;
        for (int i = 0; i < pairs.size(); i++) {
            for (int j = i+1; j < pairs.size(); j++) {
                int height = pairs.get(i).r + pairs.get(j).r;
                int width = pairs.get(i).c + pairs.get(j).c;
                if(height > h && width > w) {
                    continue;
                }
                max = Math.max(max, (pairs.get(i).r * pairs.get(i).c + pairs.get(j).r * pairs.get(j).c));
            }
        }

        bw.write(max+"");

        br.close();
        bw.close();

    }

}

2회차 정답코드

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


class Pair{

    int r;
    int c;
    int num;

    public Pair(int r, int c, int num) {
        this.r = r;
        this.c = c;
        this.num = num;
    }
}

public 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(br.readLine());

        List<Pair> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(r <= h && c <= w){
                pairs.add(new Pair(r, c, i));
            }

            if(c <= h && r <= w && r != c){
                pairs.add(new Pair(c, r, i));
            }
        }

        int max = 0;
        for (int i = 0; i < pairs.size(); i++) {
            for (int j = i+1; j < pairs.size(); j++) {
                int height = pairs.get(i).r + pairs.get(j).r;
                int width = pairs.get(i).c + pairs.get(j).c;
                if(height > h && width > w || pairs.get(i).num == pairs.get(j).num) {
                    continue;
                }
                max = Math.max(max, (pairs.get(i).r * pairs.get(i).c + pairs.get(j).r * pairs.get(j).c));
            }
        }

        bw.write(max+"");

        br.close();
        bw.close();

    }

}

문제 링크

16937번 - 두 스티커