06 Feb 2022
|
알고리즘
프로그래밍
자바
silver 4. 주유소 (13305)
출처 : https://www.acmicpc.net/problem/13305
문제
각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성
입력: 첫 줄에는 도시의 개수를 나타내는 정수 N이 주어짐. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이기 제일 왼쪽 도로부터 N-1개의 자연수로 주어짐. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어짐
출력: 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력
풀이
- 아이디어: 이전 도시의 기름값과 비교했을 때, 현재 도시의 기름값이 더 싸면 현재 도시의 기름값과 다음 도시와의 거리를 곱해 결과값에 더해주고, 이전 도시의 기름값이 더 싸면 이전 도시의 기름값과 다음 도시와의 거리를 곱해 결과값에 더해줌
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 필요한 변수 선언
int N = Integer.parseInt(br.readLine());
long[] lengths = new long[N-1]; // 도시를 연결하는 도로의 길이
long[] wons = new long[N]; // 주유소의 리터당 가격
long result = 0;
// 도로의 길이를 입력받아와 변수에 저장
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i < N-1; i++){
lengths[i] = Long.parseLong(st.nextToken());
}
// 리터당 가격을 입력받아와 변수에 저장
st = new StringTokenizer(br.readLine());
for (int i=0; i < N; i++){
wons[i] = Long.parseLong(st.nextToken());
}
long minCost = wons[0]; // 리터당 가격의 최솟값 저장. 처음 리터당 가격을 첫번째 도시의 리터당 가격으로 저장
for(int i = 0; i < N-1; i++){
if (minCost > wons[i]){ // 이전 도시와 리터당 가격을 비교했을 때, 현재 도시의 가격이 더 싼 경우
minCost = wons[i]; // 리터당 가격의 최솟값을 현재 도시의 가격으로 변경
}
result += minCost * lengths[i]; // 리터당 가격의 최솟값과 다음 도시로의 도로 길이를 곱한 후 결과값에 더해줌
}
System.out.println(result);
}
}
06 Feb 2022
|
TIL
학습과정
1. 알고리즘
silver 4. 주유소 (13305) 문제를 풀었다.
- 문제를 보았을 때 처음 생각난 아이디어는 처음 도시에서 다음 도시로 가기 위해서는 무조건 처음 도시에서 충전을 해야하므로 처음 도시의 가격과 두 번째 도시까지의 거리를 곱한 후 결과값에 저장하고, 그 다음에는 남은 도시까지의 거리의 합과 wons에 저장되어있는 값들 중 첫 번째와 마지막 값을 제외하고 최솟값을 가져와 곱해준 후 결과값에 더해주면 될 것이라고 생각했다.
- 이 아이디어는 리터당 최소 가격이 두 번째 도시의 리터당 가격일 때만 성립하기 때문에 이 아이디어로는 테스트를 통과하지 못했다.
- 다시 생각해본 결과, 리터당 최솟값을 가지고 있는 변수를 생성해 이 변수의 값과 각 도시의 리터당 가격을 비교해가면서 조건에 따라 아래의 과정을 수행하는 알고리즘으로 변경했다.
- 변수 값보다 도시의 리터당 가격이 더 싼 경우, 변수 값을 도시의 리터당 가격으로 변경해준 후 변수 값과 다음 도시와의 거리를 곱한 후 결과값에 더해준다.
- 변수 값보다 도시의 리터당 가격이 더 비싼 경우, 기존의 변수값에 다음 도시와의 거리를 곱한 후 결과값에 더해준다.
2
어제부로 자바의 정석 공부가 끝났다. 원래 오늘 스프링 공부를 위한 세팅을 진행하려 했으나… 하지 못했다.. 내일은 스프링 공부를 위한 세팅을 진행하고, “스프링 인 액션”이라는 책으로 스프링 공부를, “모던 자바 인 액션” 책으로 자바 심화 공부를 시작해야겠다.
05 Feb 2022
|
알고리즘
프로그래밍
자바
silver 5. 캠핑 (4796)
출처 : https://www.acmicpc.net/problem/4796
문제
캠핑장을 연속하는 P일 중, L일 동안만 사용 가능. V일짜리 휴가를 시작했을 때, 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)
입력: 여러 개의 테스트 케이스로 이루어짐. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있음. 모든 입력 정수는 int 범위. 마지막 줄에는 0이 3개 주어짐
출력: 각 테스트 케이스에 대해, 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력
풀이
- 아이디어:
(V / P) * L + min(L, V % P)
- min을 해주는 이유는 나머지 값보다 L의 값이 더 작을 수 있기 때문
- 2, 8, 20의 경우, V%P의 값은 4이지만 L의 값은 2. 이럴 경우 최대 2일까지만 이용 가능
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine(); // 한 줄씩 입력 받아오기
int num = 0;
while(!(line.equals("0 0 0"))){ // 입력받은 값이 "0 0 0"이 아닌 경우
num ++; // 케이스 하나 추가
StringTokenizer st = new StringTokenizer(line); // 입력받은 값을 나눠서 저장
int L = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
// 최대 며칠 있을 수 있는지 계산
int result = ((V / P) * L) + Math.min((V % P), L);
// 버퍼에 값을 써줌
bw.write("Case "+ num + ": " + result + "\n");
// 다음 줄 입력 받아옴
line = br.readLine();
}
bw.flush(); // 버퍼에 있는 값을 출력한 후
bw.close(); // 버퍼를 닫아줌
}
}
05 Feb 2022
|
TIL
학습과정
1. 자바
자바의 정석 마지막 장인 Chapter 16. 네트워킹을 공부했다.
- 클라이언트/서버
- IP 주소와 URL
- 소켓 프로그래밍: TCP와 UDP, TCP 소켓 프로그래밍, UDP 소켓 프로그래밍
2. 알고리즘
silver 4. 캠핑 (4796) 문제를 풀었다.
- 자바의 정석 입출력 부분에서 BufferedReader와 BufferedWriter를 배워 처음으로 알고리즘 문제를 풀 때 적용해보았다. 처음이다보니 직접 코드로 구현해 원하는데로 입력받아오기까지 시간이 조금 걸렸다.
- 문제를 보자마자 아이디어가 떠올라 떠오른데로 구현을 하고 제출했지만, 결과는 “틀렸습니다”가 나왔다. 왜 틀렸는지 이해가 되지 않았고 한참동안 생각했다… 틀린 이유는 처음 세운 계산식에 예외 케이스가 있었기 때문이었다.
- 처음 세운 계산식:
(V/P)*L + (V%P)
- 만약 “2 8 20”이 입력으로 들어온 경우, 처음 세운 계산식대로 계산을 하면 결과가 올바르게 나오지 않는다. V%P의 값은 4이지만 최대 사용 가능 날짜(L)의 값은 2이기 때문에 V%P의 값을 더해주면 안되고 L의 값을 더해주어야 올바른 결과가 나온다.
- 따라서 계산식을
(V/P)*L + min(L, (V%P))로 수정했고 테스트를 통과할 수 있었다.
Today Sulim Learned
