알고리즘 스터디 14주차

1. 달려달려

문제

• N분에 달릴 수 있는 거리가 주어지고, 각 학생은 N분에 달리던가 아니면 휴식을 취하던가 두가지 경우를 선택해야 한다. 달릴때마다 지침 지수가 1이 증가하고 휴식을 하면 1이 감소되는데, 휴식을 취하면 지침 지수가 0이 될 때까지 휴식을 취해야 한다. 그러면 어떻게 구성해야지 최대로 달릴 수 있을까?

풀이

• DP[x][y] = 현재 x분까지 와 있고, 지침 지수가 y일 때 최대로 달릴 수 있는 거리
• 지침지수가 1 이상인 경우 -> 휴식을 취할 수 있다.
• 지침지수 + 1 <= m인 경우 -> 달리기를 할 수 있다.
• 지침지수가 0인 경우 -> N + 1분으로 그냥 넘어갈 수 있다. (이 경우를 처리 필요!)

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
	final static BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		StringTokenizer stringTokenizer = new StringTokenizer(READER.readLine());

		int n = Integer.parseInt(stringTokenizer.nextToken());
		int m = Integer.parseInt(stringTokenizer.nextToken());

		List<Integer> runs = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			int run = Integer.parseInt(READER.readLine());

			runs.add(run);
		}

		int[][] dp = IntStream.rangeClosed(0, n).mapToObj(i -> IntStream.rangeClosed(0, m).map(j -> -1).toArray()).toArray(int[][]::new);

		System.out.println(getMaxDist(dp, runs, 0, 0, m));
	}

	private static int getMaxDist(int[][] dp, List<Integer> runs, int pos, int jis, int m) {
		if (pos >= runs.size()) {
			return 0;
		}

		if (dp[pos][jis] != -1) {
			return dp[pos][jis];
		}

		dp[pos][jis] = -1000000000;

		if (jis == 0) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + 1, jis, m));
		}

		if (jis > 0 && pos + jis <= runs.size()) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + jis, 0, m));
		}

		if (jis + 1 <= m && (runs.size() - pos - 1 - (jis + 1) >= 0)) {
			dp[pos][jis] = Math.max(dp[pos][jis], getMaxDist(dp, runs, pos + 1, jis + 1, m) + runs.get(pos));
		}

		return dp[pos][jis];
	}
}

2. 컬러볼

문제

• 공의 크기 및 색이 N개가 주어지고, 각 공은 다른 공보다 크기가 크면 삼킬 수 있다.(색이 같은 공은 못삼킴) 그러면 각 공이 얻을 수 있는 총 크기를 구하는 문제(자기 자신은 구하면 안됨)

풀이

• 아이디어는 다음과 같다. 먼저 크기가 x미만인 모든 공의 크기들의 합을 미리 구한다.(구간합) 그리고 색이 같은 크기에 대해서 x미만인 공의 크기들을 빼주면 된다.
• lsum[x] -> 크기가 x이하인 모든 공의 크기(색 상관 x)
• ballsizeList.get(x) -> 색이 x인 공들에 대한 구간합

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
	final static BufferedReader READER = new BufferedReader(new InputStreamReader(System.in));

	static class Ball {
		int c;
		int s;

		public Ball(int c, int s) {
			this.c = c;
			this.s = s;
		}
	}

	static class BallSize {
		int c;
		int sum;

		public BallSize(int c, int sum) {
			this.c = c;
			this.sum = sum;
		}
	}

	public static void main(String[] args) throws IOException {
		int n = Integer.parseInt(READER.readLine());

		int[] lSum = IntStream.rangeClosed(0, 2000).map(i -> 0).toArray();
		List<ArrayList<Integer>> sizeList = IntStream.rangeClosed(0, n).mapToObj(i -> new ArrayList<Integer>()).collect(Collectors.toList());
		Queue<Ball> queue = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(READER.readLine());
			int c = Integer.parseInt(stringTokenizer.nextToken());
			int s = Integer.parseInt(stringTokenizer.nextToken());

			queue.add(new Ball(c, s));
			sizeList.get(c).add(s);
			lSum[s] += s;
		}

		List<ArrayList<BallSize>> ballSizeList = IntStream.rangeClosed(0, n).mapToObj(i -> new ArrayList<BallSize>()).collect(Collectors.toList());

		for (int i = 1; i <= n; i++) {
			if (sizeList.get(i).isEmpty()) {
				continue;
			}

			sizeList.get(i).sort(null);
			ballSizeList.get(i).add(new BallSize(sizeList.get(i).get(0), sizeList.get(i).get(0)));
			int sum = sizeList.get(i).get(0);
			for (int j = 1; j < sizeList.get(i).size(); j++) {
				ballSizeList.get(i).add(new BallSize(sizeList.get(i).get(j), sum + sizeList.get(i).get(j)));
				sum += sizeList.get(i).get(j);
			}
		}

		for (int i = 1; i <= 2000; i++) {
			lSum[i] += lSum[i - 1];
		}

		while (!queue.isEmpty()) {
			Ball ball = queue.poll();

			int answer = lSum[ball.s - 1];

			if (ballSizeList.get(ball.c).size() > 0) {
				int idx = upper_bound(ballSizeList.get(ball.c), ball.s - 1);
				if (idx != -1) {
					answer -= ballSizeList.get(ball.c).get(idx).sum;
				}
			}

			System.out.println(answer);
		}
	}

	private static int upper_bound(List<BallSize> list, int target) {
		int l = 0;
		int r = list.size() - 1;

		while (l <= r) {
			int mid = (l + r) / 2;
			if (list.get(mid).c <= target) {
				l = mid + 1;
			} else
				r = mid - 1;
		}

		return r;
	}
}