캠핑(BJ_4796)

1. 문제 링크

https://www.acmicpc.net/problem/4796

 

---

 

2. 나의 코드

메모리: 18040 kb
시간: 256 ms
코드 길이: 755 B
시간 복잡도 : O(1)
설명
- 그리디
- 사칙연산

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_4796 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =  null;
        int idx = 1;

        while (true) {

            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            if (l == 0 && p == 0 && v == 0) break;

            System.out.printf("Case %d: %d\n", idx++, ((v / p) * l) + Math.min((v % p), l));
        }
    }
}

 

---

 

3. 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int i = 1;
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            if (l == 0 && p == 0 && v == 0) break;
            int total = l * (v / p) + Math.min(l, v % p);
            sb.append("Case " + i + ": " + total + "\n");
            i++;
        }
        System.out.print(sb);
    }
}

 

---

 

4. 배운 점

- l, p, v 의 제한은 int형 모두 이다. 그래서 O(n)도 시간이 초과된다.
- 그렇기에 무조건 O(1)의 시간복잡도를 사용해야 한다.

- 쉽다고 무시하지 말자. 항상 반례는 존재한다. Math.min((v % p), l)