C로 풀던 알고리즘을 원래 하던 자바로 다시 바꿔서 풀고 있다
42 서울에서 한 문제를 끊임없이 탐구하던 습관을 그래도 잘 가지고 나와서 이제는 문제를 다차원에서 보고
알고리즘을 먼저 해석한 뒤 풀려고 노력하게 되었다!
나무꾼 이다솜
문제
문제를 간단하게 적어보면 주어진 나무들을 전부 같은 길이로 자른 뒤
작업장에서 나무를 한 번 자를 때는, C원이 든다. 그리고, 지역 목재상에서 나무를 살 때는, 한 단위에 W원씩 준다. (다른 말로 하면, K개의 나무가 있고, 길이가 L이면, 이다솜은 K x L x W원을 벌 수 있다.)
풀이
일단 내가 틀린 이유는 여기서 최소를 1부터 시작해서 자른게 아닌 w길이부터 시작시켜서 틀렸다!
모든 경우를 전부 구해야하는데 w길이부터 구해버리면 그 전 길이들에 대한 계산을 할 수가 없었던 것!!!
이 문제는 N이 50이고 W가 10000이 최대여서 전부 돌아도 절대 시간 초과가 나지 않는다!!
문제 풀이
1. 1부터 시작해서 나무를 잘라준다
2. 만약 나무가 잘리지 않는다면 (즉 자르는것보다 작다면) 그 나무는 패스한다!
3. 각 나무를 잘라서 모두 합한 뒤 최댓값과 비교한다!
코드
import java.io.*;
import java.util.*;
public class Main {
static int N,C,W;
static int arr[];
public static void main (String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokeinzer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(br.readLine());
C = Integer.parseInt(br.readLine());
W = Integer.parseInt(br.readLine());
int arr = new int[N];
int max = 0;
for (int i =0; i< N; i++) {
arr[i] = Integer.parseInt(br.readLine());
max = Math.max(max, arr[i]);
}
long res = 0;
for (int i =1; i<=max; i++) {
long sum = 0;
for (int ij = 0; j<N; j++) {
if (arr[j] >= i) {
int cut;
if (arr[j] % i == 0) cut = arr[j] / i - 1;
else cut = arr[j] / i;
if (W * i * (arr[j] / i) - C * cut > sum )
sum += W * i * (arr[j] / i) - C * cut;
}
}
res = Math.max(sum, res);
}
System.out.println(res);
}
}근데 시간초가 C++보다 훨씬 오래 걸리고 메모리도 많이 차지했다!
-> c++ 코드와 거의 안 다른데도 시간초가 10배이상 차이여서 좀 당황했다!
그냥 언어의 속도 차이인지 어디서 잘 못 적어서 그런지 찾아봐야할 거 같다!
할리갈리 게임
이 게임을 문제로 풀거라고는 생각도 못했다..
근데 막상 풀어보니 deque로 전부 풀리는 문제였다! -> 딱 구현문제!!
풀이
이 문제는 규칙이 있는데 그걸 구현하면 되는 문제였다!
도도와 수연이는 각각의 N 장의 카드를 받는다
덱은 뒤집어 쌓는다 -> 스택처럼 뒤부터 뽑기!
각각의 카드를 내려놓는 그라운드가 있다 -> 그라운드도 계속 카드가 쌓임!
그라운드 각각을 합쳐서 5면 -> 수연이가 그라운드 카드 싹쓸이
그라운드 더미중 5가 있으면 도도가 싹쓸이, 이때 그라운드에 카드가 각각 존재하긴해야함!
카드를 가져갈때는 상대방꺼를 내 앞에 놔두고 그 다음 내 그라운드 카드를 내 현재 카드들 앞에 둔다!
코드
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Deque<Integer> doD = new ArrayDeque();
static Deque<Integer> suD = new ArrayDeque();
static ArrayList<Integer> sGround = new ArrayList();
static ArrayList<Integer> dGround = new ArrayList();
static int N,M;
public static void main(String [] args) thorws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++ ) {
st = new StringTokenizer(br.readLine());
doD.add(Integer.parseInt(st.nextToken()));
suD.add(Integer.parseInt(st.nextToken()));
}
int dNum, sNum;
while (M > 0) {
if (isEmptyDeque())
return ;
dNum = doD.pollLast();
dGround.add(dNum);
if (isEmptyDeque())
return ;
if (dNum == 5) {
doGet();
} else if (sGround.size() > 0 && dNum + sGround.get(sGround.size() - 1) == 5 ) {
suGet();
}
M--;
if (M == 0)
break;
sNum = suD.pollLast(); // su 차례
sGround.add(sNum);
if (sNum == 5) { // do 종
doGet();
} else if (dGround.size() > 0
&& sNum + dGround.get(dGround.size() - 1) == 5) { // su 종
suGet();
}
M--;
}
if (doD.size() == suD.size()) {
System.out.println("dosu");
} else {
if (doD.size() > suD.size()) {
System.out.println("do");
} else {
System.out.println("su");
}
}
}
private static boolean isEmptyDeque() {
if (doD.isEmpty() || suD.isEmpty() ) {
if (doD.size() == 0)
System.out.println("su");
else
System.out.println("do");
return true;
}
return false;
}
private static void suGet() {
while (!dGround.isEmpty())
suD.addFirst(dGround.remove(0));
while (!sGround.isEmpty())
doD.addFirst(sGround.remove(0));
}
private static void doGet() {
while (!sGround.isEmpty())
doD.addFirst(sGround.remove(0));
while (!dGround.isEmpty())
suD.addFirst(dGround.remove(0));
}
}deque 정리
