728x90

문제

 

 

접근 방식

플러그를 최소한으로 빼면서 전기용품을 사용하려면

이후에 다시 쓰일 전기용품의 플러그를 빼는 것보단

나중에 쓰일 일이 없는 플러그를 빼는 것이 효율적일 것이고

만약 나중에 쓰인다면 가장 나중에 쓰이는 것을 빼는 게 효율적이다.

 

아래와 같이 상황을 세 가지로 나누어 처리해 주면 된다.

  1. 이미 멀티탭에 꽂힌 전기용품이면 그대로 사용하면 되니 아무런 행동도 하지 않음
  2. 멀티탭에 빈 공간이 있는 경우에는 그대로 빈 공간에 꽂음
  3. 빈 공간이 없으면 앞으로 사용되지 않거나 가장 나중에 사용되는 것을 빼고 새로 꽂음

 

첫 번째 상황을 처리하기 위해 불리언 배열을 만들어

멀티탭에 꽂거나 뺄 때마다 상태를 바꿔주었고

 

두 번째와 세 번째 상황을 처리하기 위해 정수형 배열을 만들어

멀티탭에 꽂혀 있는 플러그들이 어떤 것인지 알 수 있게 저장했다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int[] history = new int[k + 1];

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= k; i++) {
			history[i] = Integer.parseInt(st.nextToken());
		}

		int tab = n;
		int[] arr = new int[n];
		boolean[] isUsed = new boolean[k + 1];
		int count = 0;

		for (int i = 1; i <= k; i++) {
			int target = history[i];
			int idx = 0;
			int late = 0;

			if (isUsed[target]) continue;
			if (tab > 0) {
				tab--;
				for (int j = 0; j < n; j++) {
					if (arr[j] == 0) {
						arr[j] = target;
						break;
					}
				}
				isUsed[target] = true;
				continue;
			}

			count++;

			for (int j = 0; j < n; j++) {
				int use = arr[j];
				int x = 0;

				for (int l = i + 1; l <= k; l++) {
					if (history[l] == use) {
						x = l;
						break;
					}
				}

				if (x == 0) {
					idx = j;
					break;
				}

				if (x > late) {
					late = x;
					idx = j;
				}
			}

			tab--;
			isUsed[arr[idx]] = false;
			isUsed[target] = true;
			arr[idx] = target;
		}

		System.out.println(count);
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 11286번 : 절댓값 힙  (1) 2024.01.21
[백준] 18808번 : 스티커 붙이기  (0) 2024.01.19
[백준] 1744번 : 수 묶기  (0) 2024.01.11
[백준] 2170번 : 선 긋기  (1) 2024.01.11
[백준] 2457번 : 공주님의 정원  (0) 2024.01.10
728x90

문제

 

 

접근 방식

주어진 수열에서 순서 상관 없이 수들을 더하거나 둘을 묶어서 곱하여

가장 큰 값을 얻기 위해서는 빼야 할 때는 가능한 가장 작은 수를

더해줄 때는 가장 큰 수를 더해줘야 한다.

 

두 수를 곱하는 경우를 생각해보면

음수 * 음수 = 양수
음수 * 0 = 0
양수 * 양수 = 양수

 

위와 같이 세 가지 경우가 있고

 

두 수를 더하는 경우를 생각해보면

양수 * 1 < 양수 + 1
양수 * 0 < 양수 + 0

 

위와 같은 경우가 있다.

 

좀 더 간단하게 정리해보면 아래와 같다.

// 음수로 만들 수 있는 최적의 해
음수 * 0이하의 수

// 양수로 만들 수 있는 최적의 해
양수 * 양수
양수 + 1

 

양수는 0과 곱하거나 더하는 경우에는 어떤 이득도 볼 수 없기 때문에

0은 위와 같이 음수와 처리해주는 것이 좋다.

 

수열을 입력 받을 때 0이하의 수가 등장할 때마다

따로 변수에 카운팅을 해준 후에

수열을 오름차순으로 정렬하면

0번 인덱스 부터 카운팅한 만큼까지가 0이하의 수에 해당하고

이후의 인덱스들은 모두 양수라는 것을 알 수 있다.

-3
-2
-1

 

위와 같은 수열이 주어졌을 때를 생각해보면

-3과 -2를 곱하여 6을 만들고 -1을 빼서 5를 얻는 경우가 최적의 해이고

-2
-1

 

위와 같은 경우는 둘이 그대로 곱해 2를 얻는 경우가 최적의 해인데

여기서 알 수 있는 것이 0이하의 개수가 홀수면

마지막 인덱스를 제외한 값들은 서로 곱하고 마지막만 빼주면 되고

개수가 짝수면 모두 서로 곱해주면 된다.

 

양수의 경우는 반대로 개수가 홀수면

첫 인덱스 값을 더해주고 나머지 값들을 서로 곱해주고

짝수면 모두 서로 곱해주면 된다.

 

이제 정리한 내용들을 토대로

0번 부터 COUNT - 1번 인덱스 까지의 음수들을 처리하는 부분과

COUNT번 부터 N - 1번 까지의 양수들을 처리하는 부분을 계산해주면 된다.

 

풀이

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());
		int count = 0;
		int[] seq = new int[n];

		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());
			seq[i] = x;
			if (x <= 0) count++;
		}

		Arrays.sort(seq);

		long prev = -1001;
		long sum = 0;

		for (int i = 0; i < count; i++) {
			int cur = seq[i];

			if (i == count - 1 && count % 2 != 0) {
				sum += cur;
				continue;
			}

			if (prev < -1000) {
				prev = cur;
				continue;
			}

			sum += (prev * cur);
			prev = -1001;
		}

		prev = -1001;

		for (int i = count; i < n; i++) {
			int cur = seq[i];

			if (i == count && (n - count) % 2 != 0) {
				sum += cur;
				continue;
			}

			if (prev < -1000) {
				prev = cur;
				continue;
			}

			if (prev * cur == cur) sum += (prev + cur);
			else sum += (prev * cur);
			prev = -1001;
		}

		System.out.println(sum);
	}
}

 

728x90

 

좀 지났지만 벌써 100일...

'Diary' 카테고리의 다른 글

새로 추가된 언어 뱃지들  (0) 2024.02.23
[백준] 128일 뱃지  (0) 2024.02.07
[백준] 오랜만에 뱃지/배경 수집  (0) 2023.12.07
[백준] 스트릭 64일  (1) 2023.12.04
[백준] 골드 달성!  (0) 2023.11.02
728x90

문제

 

 

접근 방식

1 3
2 5
3 5
6 7

 

위와 같이 일직선 상의 선분의 시작점과 끝점이 주어졌을 때

시작점이 가장 작은 순으로 정렬하고 각 선분을 그어보면

세 가지 경우로 선분을 그을 수 있는데

1 2 3 4 5 6 7
1   3
  2     5
    3   5
          6 7

 

위와 같이 처음 1-3 선분이 있을 때

다음에 오는 2-5 선분은 이전 1-3선분에 겹치면서 길이가 조금 더 긴 경우

3-5 선분은 이전 선분 자체에 모두 겹치는 경우

6-7 선분은 겹치지 않는 새로운 선분인 경우다.

 

완전히 새로운 경우에는 끝점 - 시작점으로 선분의 길이를 구할 수 있고

겹치는 경우에는 겹치지 않는 경우만 계산하면 되기 때문에

현재 선분의 끝점에서 이전 선분의 끝점을 빼주면 되고

완전히 겹치는 경우에는 계산할 필요가 없다.

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int[][] xy = new int[n][2];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(xy, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);

		int s = xy[0][0];
		int e = xy[0][1];
		int len = e - s;

		for (int i = 1; i < n; i++) {
			int x = xy[i][0];
			int y = xy[i][1];

			if (y <= e) continue;

			if (x <= e) {
				len += (y - e);
			} else {
				len += y - x;
			}

			e = y;
		}

		System.out.println(len);
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 1700번 : 멀티탭 스케줄링  (0) 2024.01.17
[백준] 1744번 : 수 묶기  (0) 2024.01.11
[백준] 2457번 : 공주님의 정원  (0) 2024.01.10
[백준] 1541번 : 잃어버린 괄호  (0) 2024.01.10
[백준] 11501번 : 주식  (1) 2024.01.10
728x90

문제

 

 

접근 방식

우선 문제를 정리해 보면

꽃이 피는 날과 지는 날이 주어졌을 때

피는 날을 포함한 날부터 꽃이 피기 시작하고

지는 날을 포함하지 않은 날까지 꽃이 피어있는다.

 

정원에 꽃이 하나라도 피어 있는 상태를 유지하기 위해선

이전에 핀 꽃이 지기 전이나 지자 마자

바로 다음 꽃이 피어 있어야 하기 때문에

이전에 심은 꽃들 중 가장 늦게 지는 날보다 

전이거나 지는 당일에 꽃이 피는 경우에만 심을 수 있다.

10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1

 

위와 같은 입력이 주어졌을 때

꽃이 빨리 피는 순서대로, 같은 경우에는 빨리 지는 순서대로

먼저 정렬을 해준다.

2, 15, 3, 23
2, 28, 4, 25
4, 12, 6, 5
5, 2, 5, 31
6, 3, 6, 15
6, 15, 9, 3
6, 15, 9, 27
7, 14, 9, 1
9, 14, 12, 24
10, 5, 12, 31

 

위의 경우에 최소한의 꽃을 심는 경우는

2.28 ~ 4.25 >> 4.12 ~ 6.5 >> 6.3 ~ 6.15 >> 6.15 ~ 9.27 >> 9.14 ~ 12.24로

5번 꽃을 심어서 정원에 꽃이 핀 상태를 유지할 수 있다.

 

우선 3월 1일 이전에 피고 이후에 지는 꽃 중에서

가장 늦게 지는 꽃을 시작점으로 한 후에

이후 나머지 꽃들의 주기를 살펴보면서

이전 꽃이 지기 전이나 직후에 필 수 있고

이전 꽃보다 늦게 지는 경우에 꽃을 심는다.

 

조심해야 할 부분은 꽃이 필 수 있는 경우라도

더 효율적인 경우 하나만을 골라야 하기 때문에

이전까지 핀 꽃들 중 가장 늦게 지는 꽃보다

오래 피는 꽃만 선택해야 한다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[][] flowers = new int[n][4];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			flowers[i][0] = Integer.parseInt(st.nextToken());
			flowers[i][1] = Integer.parseInt(st.nextToken());
			flowers[i][2] = Integer.parseInt(st.nextToken());
			flowers[i][3] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(flowers, (o1, o2) -> {
			if (o1[0] != o2[0]) {
				return o1[0] - o2[0];
			} else {
				if (o1[1] != o2[1]) {
					return o1[1] - o2[1];
				} else {
					if (o1[2] != o2[2]) {
						return o1[2] - o2[2];
					} else {
						return o1[3] - o2[3];
					}
				}
			}
		});

		int min = 0;
		int psm = 0;
		int psd = 0;
		int pem = 0;
		int ped = 0;

		for (int i = 0; i < n; i++) {
			int sm = flowers[i][0];
			int sd = flowers[i][1];
			int em = flowers[i][2];
			int ed = flowers[i][3];

			if (sm < 3 || (sm == 3 && sd == 1)) {
				if (em < pem || (em == pem && ed <= ped)) continue;
				min = 1;
				psm = sm;
				psd = sd;
				pem = em;
				ped = ed;
				if (end(pem, min))
					return;
				continue;
			}

			if (min == 0) continue;

			if (sm < psm || sm == psm && sd <= psd) {
				if (em < pem || (em == pem && ed <= ped)) continue;
				pem = em;
				ped = ed;
				if (end(pem, min))
					return;
				continue;
			}

			if (sm < pem || (sm == pem && sd <= ped)) {
				min++;
				psm = pem;
				psd = ped;
				pem = em;
				ped = ed;
			}

			if (end(pem, min))
				return;
		}

		System.out.println(0);
	}

	private static boolean end(int pem, int min) {
		if (pem > 11) {
			System.out.println(min);
			return true;
		}
		return false;
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 1744번 : 수 묶기  (0) 2024.01.11
[백준] 2170번 : 선 긋기  (1) 2024.01.11
[백준] 1541번 : 잃어버린 괄호  (0) 2024.01.10
[백준] 11501번 : 주식  (1) 2024.01.10
[백준] 2217번 : 로프  (1) 2023.12.26
728x90

문제

 

 

접근 방식

주어진 식에 적절히 괄호를 추가해 가장 작은 결과를 얻어야 하는데

간단하게 생각해 보면 - 부호가 등장한 이후에 나오는 모든 숫자들을

- 부호가 재등장하기 전까지 빼주면 된다.

55-50+40-50+40+30-50

 

예를 들어 위와 같은 식이 주어졌다면

55-(50+40)-(50+40+30)-(50)

 

이렇게 괄호를 추가해 계산하는 것이 가장 작은 결과를 얻는다.

55-((50+40)-(50+40+30)-(50))

 

조금만 더 생각해 보면 첫 - 부호 등장 이후에 오는 모든 수들은

복잡하게 생각할 필요 없이 빼도 상관이 없다는 것을 알 수 있다.

 

그래서 처음으로 -부호가 등장하기 전까지만 값을 더해주고

이후에 오는 모든 수들은 빼주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		int sum = 0;
		int len = 0;
		int num;
		char c;
		boolean isMinus = false;

		for (int i = 0; i < input.length(); i++) {
			c = input.charAt(i);

			if (Character.isDigit(c)) len++;

			if (c == '-') {
				isMinus = true;
				continue;
			}

			if (i == input.length() - 1 || !Character.isDigit(input.charAt(i + 1))) {
				num = Integer.parseInt(input.substring(i + 1 - len, i + 1));
				len = 0;

				if (isMinus) sum -= num;
				else sum += num;
			}
		}

		System.out.println(sum);
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 2170번 : 선 긋기  (1) 2024.01.11
[백준] 2457번 : 공주님의 정원  (0) 2024.01.10
[백준] 11501번 : 주식  (1) 2024.01.10
[백준] 2217번 : 로프  (1) 2023.12.26
[백준] 1931번 : 회의실 배정  (0) 2023.12.25
728x90

문제

 

 

접근 방식

싼 값에 주식을 사고 비싼 값에 팔면 가장 이득을 볼 수 있다는 당연한 사실을 통해

주어진 주가를 역으로 탐색해 현재 가장 큰 값보다 비싼 값을 만날 때까지

이전의 모든 주식을 산 후에 팔아주면 된다.

3 2 4 5 7 8 6 9 8 4 5

 

예를 들어 위와 같이 주가 목록이 주어졌을 때 역으로 탐색하면

 

5를 기준으로 더 큰 값인 8을 만나기 전까지 주식을 사면

4원에 주식을 산 후에 5원에 팔아서 1원 이득을 볼 수 있고

 

다시 8을 기준으로 더 큰 값이 9를 만나기 전까지는

어떠한 주식도 살 수 없기 때문에 8을 그대로 팔아 0원 이득을 볼 수 있으며

 

다시 9를 기준으로 더 큰 값이 없으므로 남은 모든 주식을 사면

(9원 * 7일) - (3 + 2 + 4 + 5 + 7 + 8 + 6) = 63 - 35 = 28

 

28원 만큼의 이득을 볼 수 있다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());
		int n;
		int[] arr;

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			arr = new int[n];

			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}

			long profit = 0;
			long max = 0;
			long sum = 0;
			long count = 0;

			for (int i = n - 1; i >= 0; i--) {
				long price = arr[i];

				if (max == 0) {
					max = price;
					continue;
				}

				if (i == 0) {
					if (price <= max) {
						count++;
						sum += price;
					}
					profit += (count * max - sum);
					continue;
				}

				if (max >= price) {
					count++;
					sum += price;
				} else {
					profit += (count * max - sum);
					count = 0;
					sum = 0;
					max = price;
				}
			}

			sb.append(profit).append("\n");
		}

		System.out.println(sb);
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 2457번 : 공주님의 정원  (0) 2024.01.10
[백준] 1541번 : 잃어버린 괄호  (0) 2024.01.10
[백준] 2217번 : 로프  (1) 2023.12.26
[백준] 1931번 : 회의실 배정  (0) 2023.12.25
[백준] 10844번 : 쉬운 계단 수  (0) 2023.12.24
728x90

문제

 

 

 

접근 방식

10, 30, 20, 50, 40, 80, 70, 60

 

만약 위와 같은 로프들이 주어졌을 때를 생각해보면

8개의 로프를 모두 사용한 경우에는 가장 낮은 무게를 들 수 있는

10kg짜리 로프에 맞춰야하기 때문에 80kg를 들 수 있지만

7개를 사용하는 경우에는 20kg에 맞춰서 140kg을 들 수 있다.

10, 20, 30, 40, 50, 60, 70, 80

80, 140, 180, 200, 200, 180, 140, 80

 

정렬을 해서 n개의 추를 사용하는 경우를 모두 계산해보면 위와 같다.

 

결국 정렬을 한 후에 n개를 골랐을 때마다 가능한 무게를 계산하고

그 중에서 가장 큰 값이 정답이 된다.

 

풀이

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());

		int[] weights = new int[n];

		for (int i = 0; i < n; i++) weights[i] = Integer.parseInt(br.readLine());

		Arrays.sort(weights);

		int max = 0;

		for (int i = 0; i < n; i++) max = Math.max(max, weights[i] * (n - i));

		System.out.println(max);
	}
}

 

'Java > Algorithms' 카테고리의 다른 글

[백준] 1541번 : 잃어버린 괄호  (0) 2024.01.10
[백준] 11501번 : 주식  (1) 2024.01.10
[백준] 1931번 : 회의실 배정  (0) 2023.12.25
[백준] 10844번 : 쉬운 계단 수  (0) 2023.12.24
[백준] 15486번 : 퇴사 2  (1) 2023.12.24

+ Recent posts