[SWEA] D3 - 1491번 원재의 벽 꾸미기 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b9AkKACkBBASw 

SW Expert Academy

아오 미쳐버리겠다..일단 곱한 결과가 N을 넘지 않으면서 최대한 가까운 수가 나올 수 있는 R과 C를 찾는게 관건인데

머릿속으로 생각나는 해결방법이 다 해보는 브루트포스 방법뿐이다.

근데 N이 최대 100000라서 최악의경우 다 해보면 100억이 나오게 되는데..

이중 for문으로 1부터 100000까지 다 구해보는 방식은 아닌것 같은데 달리 다른 방법이 떠오르지도 않고..

..다른 사람의 코드를 결국 참고함.

 

이중for문으로 풀되, 조건들을 넣어서 연산의 수를 많이 줄일 수 있구나..

일단 R은 N의 제곱근을 초과하지 않는 정도 까지만 본다.

예를들어 N이 25라면, 5*5까지만 확인하면 된다. 그 이상은 순서만 바뀌었지 앞에서 확인한 수 조합이기 때문에..

그리고 R*C의 결과는 N을 초과하지 않도록 한다. 주어진 타일 이상만큼은 사용할 수 없으므로..

이정도 조건을 주면 N이 100000라도 316 * 316 정도, 100000번 넘게 연산하지 않게 된다.!!

이걸 알고 나니 쉽게 풀리는 문제...눈물

 

첫번째 시도 - 테스트케이스 일부만 맞음(오답판정)

package D3;

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

public class SW_1491 {  //SWEA문제 1291번 원재의 벽 꾸미기 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //테스트 케이스 수
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long N = Integer.parseInt(st.nextToken());   //타일개수
            long A = Integer.parseInt(st.nextToken());   //가중치
            long B = Integer.parseInt(st.nextToken());   //가중치

            long min = 100000;    //최소값
            long temp = 0;
            
            for (long R = 1; R <= Math.sqrt(N); R++) {   //N의 제곱근한 수를 넘을 필요가 없음
                for (long C = R; C * R <= N; C++) { //C는 R값에서 시작해도 ㄱㅊ 중복없게 하려면
                    temp = A * (C - R) + B * (N - R * C);
                    if(temp < min)  min = temp;
                }
            }
            bw.write("#" + (t+1) + " ");
            bw.write(Integer.toString((int)min));
            bw.newLine();
        }
        bw.flush();
        bw.close();

    }
}

이유는..min 초기값으로 대충 100000을 떄려넣었기 때문이다..ㅎㅎ

아무리 최악이라도 이보다 클 순 없겠지..Long.MAX_VALUE로 아예 가장 큰 수를 넣으니 pass판정이 나왔다.

 

통과 최종코드

package D3;

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

public class SW_1491 {  //SWEA문제 1291번 원재의 벽 꾸미기 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());    //테스트 케이스 수
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long N = Integer.parseInt(st.nextToken());   //타일개수
            long A = Integer.parseInt(st.nextToken());   //가중치
            long B = Integer.parseInt(st.nextToken());   //가중치

            long min = Long.MAX_VALUE;    //min의 초기값으로 아예 가장 큰 수를 넣어버린다
            long temp = 0;

            for (long R = 1; R <= Math.sqrt(N); R++) {   //N의 제곱근한 수를 넘을 필요가 없음
                for (long C = R; C * R <= N; C++) { //C는 R값에서 시작해도 ㄱㅊ 중복없게 하려면
                    temp = A * (C - R) + B * (N - R * C);
                    if(temp < min)  min = temp;
                }
            }
            bw.write("#" + (t+1) + " ");
            bw.write(Integer.toString((int)min));
            bw.newLine();
        }
        bw.flush();
        bw.close();

    }
}