21735 눈덩이 굴리기
21735번: 눈덩이 굴리기
눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은
www.acmicpc.net
//size=눈덩이크기, pos=이동거리, time=소요시간
function back(size, pos, time){
if(pos == N or time==M) {
answer = max(answer, size)
}
}
if(i == 1) back(size+a[pos+i], pos+i, time+1)
if(i==2) back(size/2+a[pos+i],pos+i, time+1)
}
끝까지 도달하거나, 시간이 다 될 때까지 계속 앞으로 보내주면 되는데,
이때 눈덩이를 굴릴 때와 던질 때 두가지 경우만 나눠서 생각해주면 된다.
두가지 경우 뿐이기에 반복문을 사용했다.
import java.io.*;
import java.util.*;
public class tmp {
static int n, m, answer;
static int a[];
public static void backtracking(int size, int pos, int time) {
if(pos == n || time == m) {
answer = Math.max(answer, size);
return;
}
for(int i = 1; i <= 2; i++) {
if(i==1) backtracking(size+a[pos+i], pos+i, time+1);
else backtracking((size/2)+a[pos+i], pos+i, time+1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
answer = 0;
a = new int[n+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
backtracking(1, 0, 0);
System.out.println(answer);
}
}
18429 근손실
18429번: 근손실
웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로
www.acmicpc.net
주어진 운동 키트의 순서를 바꿔가면서 사용해야 하므로 사용 여부를 체크하는 used[] 배열이 필요하다.
weight가 500 미만인 경우에 가지치기를 해준다.
각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있음을 유의하자.
import java.io.*;
import java.util.*;
public class tmp {
static int n, k;
static int answer = 0;
static int a[];
static boolean used[];
public static void backtracking(int count, int weight) {
if(count == n) {
answer++;
return;
}
for(int i = 0 ; i < n; i++) {
if(used[i]==true) continue;
if(weight+a[i]-k < 500) continue;
used[i] = true;
backtracking(count+1, weight+a[i]-k);
used[i]=false;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
a = new int[n];
used = new boolean[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
backtracking(0,500);
System.out.println(answer);
}
}
12101 1,2,3 더하기 2
같이 스터디 하는 분의 해설을 참고했습니다
12101번: 1, 2, 3 더하기 2
n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.
www.acmicpc.net
k번째 경우를 어떻게 구하는가?
→ k번째가 발견됐는지 여부를 true/false로 나눠서 처리하는 방법
탐색 후에 결과가 false라면 k번째로 오는 것이 없음을 의미한다.
여기서 중요한 것은 백트래킹을 할 때 마지막 요소를 제거해주는 작업인데, 선택한 경우가 유망하지 않으면 이전 상태로 돌아가야하기 때문이다.
나같은 경우는 arraylist의 마지막 인덱스를 지워주도록 구현했다.
package baekjoon;
import java.io.*;
import java.util.*;
public class tmp {
static int n, k;
static int count = 0;
static ArrayList<Integer> li;
public static boolean backtracking(int num) {
if(num == n) {
count++;
if(count == k)
return true;
return false;
}
for(int i = 1; i <= 3; i++) {
if(num+i > n)
continue;
li.add(i);
if(backtracking(num+i)) {
return true;
}
li.remove(li.size() - 1);
//마지막 요소를 제거함으로써 복원작업.
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
li = new ArrayList<Integer>();
if(backtracking(0)) {
for(int i = 0; i < li.size(); i++)
if(i!=li.size()-1)
System.out.print(li.get(i)+"+");
else
System.out.print(li.get(i));
}
else System.out.println(-1);
}
}
'Algorithms > study log' 카테고리의 다른 글
그래프 이론 톺아보기 (0) | 2024.04.14 |
---|---|
[투포인터] 백준 20922 겹치는 건 싫어 (1) | 2024.04.09 |
[Greedy] 백준 2141 우체국 (0) | 2024.03.19 |
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |
[java] 트리와 DFS (0) | 2024.02.26 |