백준 1106, 1025

찬들이·2022년 7월 23일

알고리즘

목록 보기

12/42

문제1106(성공)

소스코드

import java.io.*;
import java.util.*;
public class boj1106 {
    static int c;
    static int n;
    static int[] value;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        c = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        value = new int[c+101];
        Arrays.fill(value, Integer.MAX_VALUE);
        value[0] = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int reward = Integer.parseInt(st.nextToken());
            for (int j = reward; j < c+101; j++) {
                int prev = value[j-reward];
                if(prev!= Integer.MAX_VALUE){
                    value[j] = Math.min(value[j], cost+prev);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = c; i < c+101; i++) {
            min = Math.min(min,value[i]);
        }
        System.out.println(min);
    }
}

풀이 접근

x원을 내서 한 번에 늘어나는 고객의 최댓 값은 100으로 제안하기 때문에 값에 대한 배열을 c+100인 배열로 만들고 배열의 값에 int변수 최대값을 넣는다.

value[0] 을 0으로 초기화하고, value[고객 수] = 비용을 만들기 위해 모든 조건에 대해서 반복문을 돌린다.

반복문의 마지막에서, 기존의 조건에 대해 최저 값이 나왔을 수도 있음으로, Math.min을 통해서 기존의 값과 새로 구해진 값을 비교해서 넣는다.

마무리로 c명 이상의 고객을 늘려야하기 때문에 value[c]부터 배열의 끝 부분까지 인덱스 중에 최솟 값을 구한 뒤 출력한다.

문제 핵심

알고리즘을 구현할 수 있는가.

문제의 조건을 잘 파악하고 배열의 크기를 잘 정했는가.

문제 1025번(실패, 문제 이해하는데 3시간)

문제 설명

0부터 9까지의 숫자로 이루어진 n행 m열의 표가 주어진다.
서로 다른 1개 이상의 칸을 선택하려고 하는데 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야한다.

( 등차가 음수여도 상관 x)

ex) 1. (0,0) (0,1)(0,2) x증가량 0 y증가량1인 등차수열

(0,0) (1,1) (2,2) x증가량 1 y증가량1인 등차수열

(2,2)(2,1)(2,0) x증가량 0 y증가량 -1인 등차수열

해당 수열로 만들어질 수 있는 값들 중 완전 제곱수를 만족하는 최대값을 구하라.
만약 완전 제곱수를 만족하는 경우가 없다면 -1을 출력해라.

소스코드

public class boj1025{
    static int[][] arr;
    static String[] input;
    static int n, m;
    static int result = -1;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        input = new String[n+1];
        for (int i = 0; i < n; i++) {
            input[i]= br.readLine();
            for (int j = 0; j < m; j++) {
                arr[i][j] = input[i].charAt(j) - '0';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                search(j,i);
            }
        }
        System.out.println(result);
    }
    public static void search(int c, int r){
        for (int i = -n; i < n; i++) {
            for (int j = -m; j < m; j++) {
                if(i ==0 &&j == 0) continue;
                int x = c;
                int y = r;
                int k =0;
                while(x>=0 && x<m &&y>=0&& y<n){
                    k*=10;
                    k += arr[y][x];
                    int root = (int)Math.sqrt(k);
                    if(Math.pow(root, 2) == k){
                        result = Math.max(result, k);
                    }
                    x+=j;
                    y+=i;
                }
            }
        }
    }
}

풀이 접근

주어진 n행 m행 표를 arr[][]배열에 저장한다.

현재 기준 좌표가 주어지고 등차가 0,0일 때를 제외하고 다른 등차수열의 경우, 합이 완전 제곱수를 만족할 때 전역변수인 result와 해당 합인 result로 Math.max를 통해 최대값을 찾아내는 함수 search를 만든다.

현재 기준 좌표 (0,0)부터 (m-1,n-1)의 좌표까지 search함수를 돌려서 나온 최대값을 출력시킨다.