주유소 서브태스크
| 2 초 | 512 MB | 70292 | 27545 | 21439 | 38.671% |
문제
어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.
처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.
예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.
제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
출력
표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.
서브태스크
| 1 | 17 | 모든 주유소의 리터당 가격은 1원이다. |
| 2 | 41 | 2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다. |
| 3 | 42 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
처음 봤을 때: 엥? 이게 무슨 말임?
난.. 컴과생이 맞나? 암튼 뭔 말인지도 모르겠더라구요
사실 읽지도 않고 그 생각 하고 걍 베린 거기도 함.
그럼 이제 읽어 볼게요. (진짜 지금 처음 읽음)
나라에 도시가 n개 있다 오호 서울 부산 광주 어쩌고~
오.. 제일 왼쪽에서 제일 오른쪽... 대충 서울에서 부산 간다고 칩시다... srt처럼 경유를 하는 거죠....
서울에서 기름 넣고 출발 기름통 크기 무제한이라 기름 개많이 넣을 수 잇음 오호 1키로에 1리터 사용....
아하 저 선 위에 있는 숫자가 거리고 동그라미 안에 있는 숫자가 기름값이었습니다! 역시 서울이 기름이 비싸네요!
제일 싸게 끝까지 가는 값을 푸는 거였습니다 최저가 찾기~~
입력값 1: 도시 개수 == 동그라미 개수(2 <= n <= 100000)
입력값 2: 도로 길이 == 짝대기 위 숫자 순서대로(n-1개)
입력값 3: 리터당 가격 == 동그라미 안의 숫자(n개)
근데 쓰다 보니까 기름을 많이 담아갈수록 차가 무거워지니까 사용하는 기름 양도 많아지는 거 아닌가 라는 의문이 조금 들긴 하는데요 더 복잡해지니까 그 생각은 접어두기로 합시다..
출력 부분까지 읽고
백준 초보는 서브태스크를 보고 당황하기 시작합니다.
이게 모지?????
근데 읽어보니까 중간고사 기말고사 부분 점수 같은 존재였음ㅇㅋㅇㅋ
그러면
1번부터 푸는 건가...?
일단 1번부터 풀어보기로...
-> 라는 건 백알못의 헛소리였습니다. 보니까 그냥 다 저 조건에 들어맞아야 한다는 것 같기도
모든 주유소의 리터당 가격은 1원이다. 지역 상관없이 공평한 1원? 대형마트에서 사나 봅니다.
2 <= n <= 1000이고 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터당 가격은 최대 10,000이다...
뭔 소린지 모르겠고
일단 풀어볼게요!
갑자기 입력 부분부터 고민하게 됨
저 동그래미들은 배열로 받아야겟지 역시? 그러면 저 짝대기들도?
입력 부분을 만들고 뿌듯하게 있다가 최저가 알고리즘을 급하게 생각하기 시작했다.
어떻게 하면 최저값이냐구...? 기름을 제일 싸게 사는 게 최저가겠지요... 그러면 일단 비싼 곳에서는 도착지까지의 기름만 있어야 하고 싼 데서 최대한 많이 쟁여야 한다 근데 그걸 어떻게 아냐구??
1. 일단 맨 처음 기름을 넣긴 넣어야 한다 두 번째 갈 정도까지는...
2. 현재 있는 도시보다 바로 오른쪽 도시 기름값이 더 싸면 딱 갈 정도까지만 넣으면 되지 않나?
3. 오른쪽 도시 기름값이 더 비싸면? 그 다음 도시 갈 정도까지 넣어야겠지
4. 그 다음 도시도 기름값이 비싸면?????
무한 비싸면의 굴레....
근데 생각해보면 또 맞는 것 같기도 하다.
이걸 코드로 어떻게 구현하느냐가 문제인데 그러면 기름값 비교를 한 담에 기름값 * 거리를 계속 total에 넣어주면 될라나??
일단 다시 짜볼게여
코드는 안 짜고
떡튀순오를 조지고 왔다.
다시 해봐야지
import java.util.Scanner;
public class BJ_13305 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 도시 개수
int n = sc.nextInt();
// 거리
int[] length = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
length[i] = sc.nextInt();
}
// 기름 가격
int[] price = new int[n];
for (int i = 0; i < n - 1; i++) {
price[i] = sc.nextInt();
}
int total = 0;
for (int i = 0; i < n - 1; i++) {
if (price[i] >= price[i + 1]) {
total += price[i] * length[i];
}
else {
total += price[i] * (length[i] + length[i + 1]);
}
}
System.out.println(total);
sc.close();
}
}처음 짠 코드...
1차로 컴파일 에러가 나고(public 안 지움) 다시 돌리니 런타임 에러가 났다.
역시 너무 생각을 안 해서인가...?????
| main class Main | Error: Could not find or load main class Main |
뭐냐 넌
-> 클래스 이름 문제였다 Main으로 바꾸니까 정상 작동
하지만!! 17점이었다.ㅎ
그래.. 역시 생각을 안 해서 그래.... 이클립스 콘솔에 돌려봤는데 예제 1번부터 틀리더라
생각하다보니 무조건 최저가를 찾는다... 예전에 들었던 자료구조 수업이 떠오르면서 탐욕 알고리즘인가?! 라는 생각이
Greedy Algorithm~
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 도시 개수
int n = sc.nextInt();
// 거리
int[] length = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
length[i] = sc.nextInt();
}
// 기름 가격
int[] price = new int[n];
for (int i = 0; i < n - 1; i++) {
price[i] = sc.nextInt();
}
int total = 0;
for (int i = 0; i < n - 1; i++) {
// 오른쪽 도시 기름값이 왼쪽 도시 기름값보다 쌀 때
if (price[i] >= price[i + 1]) {
total += price[i] * length[i];
}
else {
total += price[i] * (length[i] + length[i + 1]);
i++;
}
}
System.out.println(total);
sc.close();
}
}2차 수정
근데 똑같이 17점이다 쪼금 더 생각해서 한 칸 더 옆으로 보내줬는데...
뭐가 문제지???
하긴 1번 도시 기름값이 3번 도시 기름값보다 쌀 경우 이런 경우를 간과했다. 그럼 다시 수정....~~
그럼 최소값을 찾아야 하나??
기름 가격은 n개 받아야 하는데 n - 1개로 받고 있었다.. 17점이 나온 게 신기한 수준
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 도시 개수
int n = sc.nextInt();
// 거리
int[] length = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
length[i] = sc.nextInt();
}
// 기름 가격
int[] price = new int[n];
for (int i = 0; i < n; i++) {
price[i] = sc.nextInt();
}
int total = 0; // 비용 초기화
int min = price[0]; // 일단 첫 번째 기름값을 min으로 잡음
for (int i = 0; i < n - 1; i++) {
if (price[i] < min) {
min = price[i]; // 여기보다 싼 곳 있으면 min에 넣기
}
total += min * length[i]; // 최저가 가격으로 갈 수 있는 곳까지 가기
}
System.out.println(total);
sc.close();
}
}
그리디 알고리즘!!! 하면서 생각하니 오른쪽 하나하나 생각할 거 없이 최저가 찾으면 밀고나가다가 더 싼 곳 찾으면 그걸로 밀고 나간다 라고 짜니 생각보다 더 간단했다.
문제는
ㅎㅇ 나 58점....
서브태스크가 괜히 있는 게 아니구나 싶었다.
무서운 백준... 사람을 이렇게 간파하다니
17 -> 58 차근차근 백준의 계획대로다.
2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
조건을 보니 타입 문제 같다 그러면 얘를 키워줘야지.. long 타입으로 바꿔줘야하나?!! 근데 java long 있는 건 아는데 long long 타입이 있는 지 갑자기 궁금해짐 -> 없대요
int 타입은 21억까지 되잖아요 근데 문제 보니까 거리 10억까지(총 길이) 기름은 리터당 가격이 10억까지도 되더라(이 정도면 세상 망한 듯) 그러면 총합이 21억 넘을 수도 있겠네..
귀찮아서 모든 걸 다 long 타입으로 바꿔버릴까 하다가 일단 쪼금만 바꿔보자 하고서 결과값 담는 total만 long으로 바꿨다가 또 58점을 받았다.
이유는 ... 뭘까?
암만 봐도 배열을 long으로 할 이유는 없는 것 같다. 10억이면 int로 충분히 커버되는 범위라 굳이 long을 쓸 필요가...?
한 번 고민하고 나니 절대 모든 걸 long으로 바꾸기 싫어졌다.
한참 생각해보다 total에 넣어주는 기름값 연산할 때가 문제인가?? 하고 그 부분도 타입 변환으로 고쳐줬다.
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 도시 개수
int n = sc.nextInt();
// 거리
int[] length = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
length[i] = sc.nextInt();
}
// 기름 가격
int[] price = new int[n];
for (int i = 0; i < n; i++) {
price[i] = sc.nextInt();
}
long total = 0; // 비용 초기화, 21억 넘을 수도 있으니까 long 타입
int min = price[0]; // 일단 첫 번째 기름값을 min으로 잡음
for (int i = 0; i < n - 1; i++) {
if (price[i] < min) {
min = price[i]; // 여기보다 싼 곳 있으면 min에 넣기
}
total += (long) min * length[i]; // 최저가 가격으로 갈 수 있는 곳까지 가기, 곱했을 때 int 초과할 수도 있으니까 타입 변환
}
System.out.println(total);
sc.close();
}
}
total만 long 타입으로 변환
total에 더해줄 때 우변 (long) 변환 추가
결과는?
오예~
승리(ㅂㅂX)다 이거야~
오늘의 결론
1. 문제를 잘 읽자 괜히 교수님이 문제 읽기가 제일 중요하다는 말을 하신 게 아님
2. 백준의 서브태스크는.. 괜히 있는 게 아니구나
3. 처음 생각을 잘 하자
끝!
'백준 풀기' 카테고리의 다른 글
| 백준 15655번: N과 M (6) with Java (0) | 2024.07.12 |
|---|---|
| 백준 1004번: 어린 왕자 with Java (0) | 2024.07.11 |
| 백준 2559번: 수열 with Java (0) | 2024.07.07 |
| 백준 15657번: N과 M(8) with Java (1) | 2024.07.05 |
| 백준 9375번: 패션왕 신해빈 with Java (0) | 2024.07.04 |