- 풀이
왼쪽으로 오른쪽으로 가면서 현재까지의 주유소 중 리터당 가장 적은 가격을 요구하는 주유소의 가격을 더한다.
예제 입력 1)로 예시를 들면,
2km를 가야하기 때문에 최소 2리터의 기름이 필요하다.
주유소는 리터당 5를 요구하는 주유소밖에 없으므로 1리터당 5원을 내고 주유를 한다.
그 후 3km를 가야하는데 그 전의 리터당 5원을 요구하는 주유소보다 더 적은 값을 요구하는 리터당 2원을 요구하는 주유소가 있으므로 리터당 2원의 주유소에서 3리터를 주유한다.
마지막으로 1km를 가야한다. 현재 도착한 주유소는 리터당 4원을 요구한다. 도착한 주유소보다 리터당 2원이라는 적은 금액을 요구하는 주유소가 있으므로 더 적은 금액을 요구하는 주유소에서 주유한다.
최종적으로 5*2 + 2*3 + 2*1 = 18 이라는 가장 적은 금액으로 맨 오른쪽까지 갈 수 있다.
이러한 알고리즘은 왼쪽에서 오른쪽으로가며 리터당 가장적은 주유소 가격을 유지하고 있으면 된다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
public class Main {
static int N;
static long answer;
static long[] gasStation, distance;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
answer = 0;
distance = new long[N-1];
gasStation = new long[N];
for(int i = 0; i < N-1; i++) {
distance[i] = in.nextLong();
}
for(int i = 0 ; i < N; i++)
gasStation[i] = in.nextLong();
SaveAnswer();
}
private static void SaveAnswer() {
long minGasStation = gasStation[0]; // 이전 까지의 과정 중 주유 최소 비용
for(int i = 0; i < N - 1; i++) {
if(gasStation[i] < minGasStation) {
minGasStation = gasStation[i];
}
answer += (minGasStation * distance[i]); // 총 비용 누적 합
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- 시간초과 났던 잘못 짠 코드
모든 방법을 체크하는 브루트포스 형식의 알고리즘으로 짜보았다. N이 10만까지라 시간초과가 날 것 같았고, 시간초과는 역시나 났다.
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.InputMismatchException;
public class Main {
static int N, answer;
static int[] gasStation, distance;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
answer = Integer.MAX_VALUE;
distance = new int[N-1];
gasStation = new int[N];
int totalDistance = 0;
for(int i = 0; i < N-1; i++) {
distance[i] = in.nextInt();
totalDistance += distance[i];
}
for(int i = 0 ; i < N; i++)
gasStation[i] = in.nextInt();
SaveAnswer(totalDistance, 0, 0);
}
private static void SaveAnswer(int remainDistance, int nowIndex, int usingGas) {
if(remainDistance == 0) {
answer = Math.min(answer, usingGas);
return;
}
int now = nowIndex;
for(int i = nowIndex ; i < N-1; i++) {
usingGas += distance[i] * gasStation[now];
remainDistance -= distance[i];
nowIndex++;
SaveAnswer(remainDistance, nowIndex, usingGas);
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 1303번 : 전쟁 - 전투 (0) | 2021.08.02 |
|---|---|
| [BOJ/JAVA] 백준 2504번 : 괄호의 값 (0) | 2021.08.02 |
| [Programmers/JAVA] 2020 KAKAO BLIND RECRUITMENT - 문자열 압축 (0) | 2021.05.01 |
| [Programmers/JAVA] 2021 KAKAO BLIND RECRUITMENT - 신규 아이디 추천 (0) | 2021.05.01 |
| [BOJ/JAVA] 백준 17143번 : 낚시왕 (0) | 2021.04.20 |
