공부 기록

1~n 까지 합 n(n+1)/2 <= S 의 방정식을 풀면 된다.

이 방정식을 풀면 n^2+n-2S<=0 이고, 방정식의 해를 구하면 n이 (-1+√ (1+8s))/2 와 (-1-√ (1+8s))/2 사이에 있으면 되고, 그 중에 큰 값이므로 (-1+√ (1+8s))/2을 버림하여 구하면 된다. 풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long n = (long) ((-1 + Math.sqrt(1 + 8 * s)) / 2);

		System.out.println(n);

	}
}

근데 문제 조건에 이분탐색으로 풀라는 이야기가 있었기 때문에.. 이분탐색으로 풀어보자면

n(n+1)/2를 s와 비교하여 아래와 같이 이분탐색으로 풀 수도 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		long s = in.nextLong();
		long end = s;
		long start = 0;
		long answer = 0;

		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = sum(mid);

			if (sum <= s) {
				answer = Math.max(answer, mid);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}

		System.out.println(answer);
	}

	private static long sum(long n) {
		return n * (n + 1) / 2;
	}
}

자리수가 가장 높은 알파벳에 순서대로 높은 값을 부여하면 되는 문제이다.

그렇지만 캐리 등이 있을 수 있다는 점을 염두해서 문제를 풀도록 해야한다.

이를 위해 예시 GCF + ACDEB의 경우

(100G+10C+1F)+(10000A+1000C+100D+10E+1B)로 변환하여

10000A+1010C+100D+100G+10E+1F+1B로 계산하고, 계수가 높은 순으로 높은 숫자를 부여해서 계산하도록 하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int alphabets[] = new int[26];

		for (int i = 0; i < n; i++) {
			String str = in.next();
			char ch[] = str.toCharArray();
			int index = 1;

			for (int j = ch.length - 1; j >= 0; j--) {
				alphabets[ch[j] - 'A'] += index;
				index *= 10;
			}
		}

		PriorityQueue<Alphabet> queue = new PriorityQueue<Alphabet>();
		for (int i = 0; i < alphabets.length; i++) {
			queue.add(new Alphabet(i, alphabets[i]));
		}

		int index = 9;
		int sum = 0;
		while (!queue.isEmpty()) {
			Alphabet alphabet = queue.poll();
			sum += alphabet.value * index;
			index--;
		}

		System.out.println(sum);
	}
}

class Alphabet implements Comparable {
	int index;
	int value;

	public Alphabet(int index, int value) {
		this.index = index;
		this.value = value;
	}

	@Override
	public int compareTo(Object o) {
		Alphabet alphabet = (Alphabet) o;
		return -Integer.compare(this.value, alphabet.value);
	}
}

치즈는 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉하면 녹는다.

이 때, dfs를 돌며 바로바로 치즈를 녹이는 식으로 문제를 풀면 안되고, 미리 어떤 치즈가 녹을지 체크를 한 뒤 해당 체크 부분만 녹이도록 해야 한다.

풀이는 아래와 같다.

import java.util.*;

public class Main {
	public static int[] dr = { 0, 0, 1, -1 };
	public static int[] dc = { 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int time = 0;
		while (true) {
			boolean isVisited[][] = new boolean[n][m];
			boolean isMelted = false;

			dfs(0, 0, n, m, mat, isVisited);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (mat[i][j] == 1 && meltCheese(i, j, n, m, mat)) {
						isMelted = true;
					}
				}
			}

			if (!isMelted) {
				break;
			}
			time++;
		}
		System.out.println(time);
	}

	private static void dfs(int r, int c, int n, int m, int[][] mat, boolean[][] isVisited) {
		mat[r][c] = -1;
		isVisited[r][c] = true;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] != 1 && !isVisited[row][col]) {
				dfs(row, col, n, m, mat, isVisited);
			}
		}
	}

	private static boolean meltCheese(int r, int c, int n, int m, int mat[][]) {
		int airs = 0;
		for (int i = 0; i < 4; i++) {
			int row = r + dr[i];
			int col = c + dc[i];
			if (isBoundary(row, col, n, m) && mat[row][col] == -1) {
				airs++;
			}
		}
		if (airs >= 2) {
			mat[r][c] = 0;
			return true;
		}
		return false;

	}

	private static boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow) {
			return false;
		}
		if (col >= maxCol) {
			return false;
		}
		return true;
	}
}

1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다.

문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다.

문제 조건

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이 문제는 순서가 있다. 기본적으로 위상정렬을 이용 + 크기순으로 순회하면 될 것이라고 생각했다.

크기순으로 순회하기 위해서 PriorityQueue를 사용하도록 했다. 풀이는 아래와 같다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Integer> childs[] = new LinkedList[v + 1];
		LinkedList<Integer> parents[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			childs[i] = new LinkedList<Integer>();
			parents[i] = new LinkedList<Integer>();
		}

		int[] parentNum = new int[v + 1];

		for (int i = 0; i < e; i++) {
			int parentNode = in.nextInt();
			int childNode = in.nextInt();

			childs[parentNode].add(childNode);
			parents[childNode].add(parentNode);
			parentNum[childNode]++;
		}

		traverseProblems(parentNum, childs, parents);
	}

	public static void traverseProblems(int[] parentNum, LinkedList<Integer> childs[], LinkedList<Integer> parents[]) {
		int problemNum = parentNum.length;
		boolean[] isVisited = new boolean[problemNum];

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for (int i = 1; i < problemNum; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;
			System.out.print(now + " ");

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);
				}
			}
		}
	}
}

1~N까지 특정한 최단 경로를 구할 때, 임의로 주어진 두 정점은 반드시 통과하도록 하는 문제이다.

일단 두 점 A, B은 무조건 통과해야 하므로 최단 경로는 `1~A~B~N` 또는 `1~B~A~N`이 될 수 있다.

따라서 1, A, B에서 다익스트라를 각각 돌려서 다른 점까지를 구한 다음에 두가지 최단경로를 비교하여 최솟값을 구했다.

구현 코드는 아래와 같다.

import java.util.*;

public class Main {
	public static long MAX = 800 * 200000 * 1000 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
			mat[end][start] = Math.min(mat[end][start], weight);
		}

		int A = in.nextInt();
		int B = in.nextInt();

		long distanceFrom1[] = dijkstra(1, n, mat);
		long distanceFromA[] = dijkstra(A, n, mat);
		long distanceFromB[] = dijkstra(B, n, mat);

		long ans = -1;

		if (distanceFrom1[A] < MAX && distanceFromA[B] < MAX && distanceFromB[n] < MAX) {
			ans = distanceFrom1[A] + distanceFromA[B] + distanceFromB[n];
		}
		if (distanceFrom1[B] < MAX && distanceFromB[A] < MAX && distanceFromA[n] < MAX) {
			ans = Math.min(ans, distanceFrom1[B] + distanceFromB[A] + distanceFromA[n]);
		}
		System.out.println(ans);
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}

		return dist;
	}
}

내가 푼 방법이 다른 스터디원보다 월등히 느려서... 나중에 코드 비교를 좀 해봐야겠다ㅠ

k진 트리에서 두 노드 사이의 거리를 구하는 문제이다.

공통 조상문제와 유사한데, 각 노드에서 공통 조상까지의 거리를 구한 뒤 더하면 된다.

주의할 점은 노드의 수가 10^15이므로 long 타입을 사용해야 한다.

이때 k == 1인 경우는 트리의 높이가 log단위가 아니고 한 개로 쭉 나열 되어 있으므로 따로 먼저 높이 차를 리턴해주면 된다.

​

k진 트리를 보면서 규칙을 찾아보자

정점 long A의 부모노드가 (A-2)/k + 1임을 알 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long n = in.nextLong(); // 노드 수
		int k = in.nextInt(); // k진 트리
		int test = in.nextInt();

		for (int t = 0; t < test; t++) {
			long x = in.nextLong();
			long y = in.nextLong();

			if (k == 1) {
				System.out.println(Math.abs(x - y));
				continue;
			}

			long distance = 0;
			while (x != y) {
				long max = Math.max(x, y);
				y = Math.min(x, y);
				x = (max - 2) / k + 1;
				distance++;
			}
			System.out.println(distance);
		}
	}
}

2021/01/17 - [알고리즘 공부] - SWEA 1248: 공통조상

문제 조건

고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면,

두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. => 기울기를 생각해 주어야 한다.

가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 문제이다.

백준에 나와있는 예시를 그려보면 아래와 같고, index=12일 때, 볼 수 있는 빌딩의 경우 선을 연결해 보면

빌딩을 기준으로 왼쪽으로 갈때나 오른쪽으로 가면서 볼 때 기울기가 커져야 한다.

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

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int building[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			building[i] = in.nextInt();
		}

		System.out.println(checkAllBuilding(building, n));
	}

	public static int checkAllBuilding(int[] building, int n) {
		int max = 0;

		for (int i = 1; i <= n; i++) {
			int sum = calcGradient(building, i, n, 1) + calcGradient(building, i, n, -1);
			max = Math.max(max, sum);
		}

		return max;
	}

	public static int calcGradient(int[] building, int index, int n, int dx) {
		if ((index == 1 && dx < 0) || (index == n && dx > 0)) {
			return 0;
		}

		int num = 1;
		int checkIndex = index + dx;
		long gradientY = building[index] - building[checkIndex];
		long gradientX = index - checkIndex;

		while (true) {
			checkIndex += dx;
			if (checkIndex <= 0 || checkIndex > n) {
				break;
			}

			long nextGradientY = building[index] - building[checkIndex];
			long nextGradientX = index - checkIndex;
			if (isPossible(gradientY, gradientX, nextGradientY, nextGradientX, dx)) {
				gradientY = nextGradientY;
				gradientX = nextGradientX;
				num++;
			}
		}
		return num;
	}

	public static boolean isPossible(long gradientY, long gradientX, long nextGradientY, long nextGradientX, int dx) {
		if (dx > 0) { // 포인터가 오른쪽으로 움직이고 있는 경우 - 기울기가 증가해야 함
			return nextGradientY * gradientX > gradientY * nextGradientX;
		}

		// 포인터가 왼쪽으로 움직이고 있는 경우 - 기울기가 감소해야 함
		return nextGradientY * gradientX < gradientY * nextGradientX;
	}
}

처음에는 double 형으로 기울기를 계산해 주었는데, double의 경우 유효숫자 개수가 정해져 있어서 이렇게 풀면 틀린댄다..

float 형은 부호 (1bit) + 지수 (8bit) + 가수 (23bit) = 32bit = 4byte로 이루어져 있다. => 유효 숫자가 6자리
double 형은 부호 (1bit) + 지수 (11bit) + 가수 (52bit) = 64 bit = 8byte로 이루어져 있다. => 유효 숫자가 15자리

수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다.

• 수빈이가 움직이는 방법: X - 1, X + 1, 2 * X
• 동생이 움직이는 방법: K + 1 + 2 + 3 + ... + i
• 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

수빈이가 왼쪽한번 오른쪽한번 이동하게 되면 제자리로 돌아오기 때문에, 짝수/홀수 시간마다 갈 수 있는 곳을 나누어 시간을 저장한다.

만약 동생이 지나가는 좌표값에 수빈이가 처음 도착하는 시간이 더 빠를 경우 답을 업데이트 해 주도록 한다.

import java.util.*;

public class Main {
	public static int INF = 500000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int indexSubin = in.nextInt();
		int indexSister = in.nextInt();

		int isVisited[][] = new int[INF + 1][2];
		for (int i = 0; i <= INF; i++) {
			isVisited[i][0] = -1;
			isVisited[i][1] = -1;
		}

		moveSubin(isVisited, indexSubin);
		System.out.println(moveSister(isVisited, indexSister));
	}

	public static void moveSubin(int[][] isVisited, int start) {
		Queue<Move> queue = new LinkedList<Move>();
		queue.add(new Move(start, 0));
		isVisited[start][0] = 0;

		while (!queue.isEmpty()) {
			Move now = queue.poll();

			int nextTime = now.time + 1;
			checkBoundaryAndPushQueue(isVisited, queue, now.index - 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index + 1, nextTime);
			checkBoundaryAndPushQueue(isVisited, queue, now.index * 2, nextTime);
		}
	}

	public static void checkBoundaryAndPushQueue(int[][] isVisited, Queue<Move> queue, int index, int time) {
		if (isBoundary(index) && isVisited[index][time % 2] == -1) {
			queue.add(new Move(index, time));
			isVisited[index][time % 2] = time;
		}
	}

	public static int moveSister(int[][] isVisited, int start) {
		for (int time = 0; time < INF; time++) {
			int index = start + time * (time + 1) / 2;

			if (index > INF) {
				return -1;
			}

			if (isVisited[index][time % 2] != -1 && isVisited[index][time % 2] <= time) {
				return time;
			}
		}
		return -1;
	}

	public static boolean isBoundary(int index) {
		if (index < 0) {
			return false;
		}
		if (index > INF) {
			return false;
		}
		return true;
	}
}

class Move {
	int index;
	int time;

	public Move(int index, int time) {
		this.index = index;
		this.time = time;
	}

	@Override
	public String toString() {
		return "(" + index + ": " + time + ")";
	}
}