📙 Algorithm Solving/Java
📙[Algo] 24.02.13 알고리즘
혜덕hyeduck
2024. 2. 14. 12:07
알고리즘 문제) BOJ 20159. 동작 그만. 밑장 빼기냐?
문제 요약
- N개의 카드와 2명의 플레이어
- N은 짝수개가 주어짐
- 카드를 분배했을 때 카드 윗장에 적힌 수의 합이 더 큰 사람이 이김
- 카드는 분배한 사람부터 받는다.
- 한번만 밑장 빼기를 할 때 얻을 수 있는 최대 카드 합?
- 밑장 빼기 : 윗장이 아닌 밑장을 보여
시간 제한
- 2초
입력
- 카드 개수 N
- 2≤N≤10만, 짝수
- 카드의 윗장부터 밑장까지 카드의 값 X가 정수로 주어짐
- 1≤X≤1만
출력
- 정훈이가 얻을 수 있는 최대 카드 합?
접근법
- 밑장빼기 이해가 어려웠던 문제.. ⇒ 잘 못 이해하고 풀어서 틀림;;;;
- 해당 턴에서 밑장을 빼면 밑장에 있는 카드를 해당 턴에 받게 되고, 그만큼 카드가 밀리게 됨 ⇒ 즉 원해 홀수번째 받아야했다면 밑장뺴는 순간부턴 짝수번째를 받게 된다.
3 2 5 2 1 3
- 밑장 빼기 안 할 경우
- 정훈 : 3 5 1 (1, 3, 5)
- 상대 : 2 2 3 (2, 4, 6)
- 1 턴에서 밑장 빼기
- 정훈 : 3 2 2 (6, 2, 4)
- 상대 : 5 1 3 (3, 5, 1)
- 2턴에서 밑장 빼기(상대방)
- 정훈 : 3 2 2 (1, 2, 4)
- 상대 : 3 5 1(6, 3, 5)
- 3턴에서 밑장 빼기
- 정훈 : 3 3 2(1, 6, 4)
- 상대 : 2 5 1(2, 3, 5)
- 4턴에서 밑장 빼기
- 정훈 : 3 5 2 (1, 3, 4)
- 상대 : 2 3 1 (2, 6, 5)
- 5턴에서 밑장 빼기
- 정훈 : 3 5 3 (1, 3, 6)
- 상대 : 2 2 1 (2, 4, 5)
⇒ 밑장빼기를 했을 때
- 밑장빼기를 안 할수도 있으니까 answer 값 초기값은 밑장빼기를 안 했을 때로 초기화
- 정훈이 차례에서 밑장 뺐을 경우
- 그 전까지는 홀수번째 카드를 받고,
- 해당 차례에서 N번째 카드(밑장)을 받고,
- 그 이후에는 짝수번째 카드를 받는다.
- ⇒ odd[i-1] + arr[N] + even[N] - even[i-1]
- 상대방 차례에서 밑장 뺐을 경우
- 그 전까지는 홀수번째 카드를 받고,
- 해당 차례부터는 짝수번째 카드를 받는다.
- ⇒ odd[i-1] + even[N] - even[i-1]
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] odd = new int[N + 1];
int[] even = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
if (i % 2 == 1) {
// 홀수 번째
odd[i] = odd[i - 1] + Integer.parseInt(st.nextToken());
even[i] += even[i - 1];
} else {
// 짝수 번째
even[i] = even[i - 1] + Integer.parseInt(st.nextToken());
odd[i] += odd[i - 1];
}
}
int answer = odd[N - 1];
for (int i = 1; i < N; i++) {
if (i % 2 == 1) {
// 정훈이 차례 밑장 빼기
answer = Math.max(answer, odd[i - 1] + even[N] - even[i - 1]);
} else {
// 상대방 차례 밑장 빼기
answer = Math.max(answer, odd[i - 1] + even[N - 1] - even[i - 1]);
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 22945. 팀 빌딩
문제 요약
- 개발자 N명이 팀빌딩을 위해 한 줄로 서있다.
- 팀의 능력치
- (개발자 A와 개발자 B 사이에 존재하는 다른 개발자 수) * min(개발자 A의 능력치, 개발자 B의 능력치)
- 나올 수 있는 팀 중 능력치 최대값?
시간 제한
- 1초
입력
- 개발자수 N
- 2 ≤ N ≤ 10만
- 능력치 xi가 공백으로 주어짐
- 1 ≤ xi ≤ 1만, xi는 정수
출력
- 팀의 능력치 최대값?
접근법
- 완전 탐색으로 접근하기
- 2중 for문 사용해서 시작점(개발자A)과 끝점(개발자B)을 정한다.
- ⇒ 그러나 N이 10만까지 가능하기 때문에 불가능
- 최적화 (투 포인터)
- 1 4 2 5
s e - 팀 능력치는 두 가지를 고려해야 함
- A,B사이에 존재하는 개발자 수
- min(개발자A 능력치, 개발자B 능력치)
- s→1, e→N을 가리킨 상태에서 시작한다
- 즉 1번 항목이 최대가 되는 경우 부터 시작
- 그 다음은 능력치에 따라 결과 값이 바뀐다. 개발자수의 경우 더 작아질일밖에 없음
- 그러면 능력치가 작은쪽을 더 키우는 방향으로 가야함
- arr[s] < arr[e] 라면 s+=1
- arr[s] ≥ arr[e] 라면 e-=1
- 그러면 능력치가 작은쪽을 더 키우는 방향으로 가야함
- 1 4 2 5
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int s = 0, e = N - 1;
int answer = 0;
while (s <= e) {
answer = Math.max(answer, (e - s - 1) * Math.min(arr[s], arr[e]));
if(arr[s] < arr[e]) s++;
else e--;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 27172. 수 나누기 게임
문제 요약
- 모든 플레이어가 본인을 제외한 다른 플레이어와 한 번씩 결투를 해야 끝난다.
- 게임은 아래와 같이 진행
- 1~100만사이 수가 적힌 카드들을 한 장씩 나눠 가짐
- 플레이어끼리 서로 카드를 보여줬을 때 상대방 카드 % 본인 카드가 0이면 승리
- 승리 : +1
- 패배 : -1
- 무승부 : 변화 X
- 게임 종료 후 모든 플레이어의 점수 구하기
시간 제한
- 1초
입력
- 플레이어 수 N
- 2≤N≤10만
- N번째 플레이어까지 각 카드에 적힌 정수가 공백으로 주어짐 xi
- 1 ≤ xi ≤ 100만
- 중복된 수 X
출력
- 각 플레이어의 점수를 공백으로 구분해 출력
접근법
- 완전 탐색으로 접근하기
- 2중 for문을 사용해서 플레이어끼리 비교한다.
- ⇒ 하지만 N이 10만까지 가능하기 때문에 for문은 1개만 사용 가능
- 최적화 하기
- 우선 1000000크기의 배열을 만든다. (check, score)
- check : 현재 숫자 카드 존재 여부 체크
- score : 점수 기록
- 입력 받을 때마다 check[x] = true; 를 진행한다.
- for문을 통해 x를 순회하면서
- x의 약수를 구한다
- if(check[약수])
- score[x] += -1
- score[약수] += +1
- if(check[약수])
- x의 약수를 구한다
- 우선 1000000크기의 배열을 만든다. (check, score)
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
boolean[] check = new boolean[1000010];
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
check[arr[i]] = true;
}
int num;
int[] score = new int[1000010];
for (int i = 0; i < N; i++) {
num = arr[i];
// 약수 구하기
for (int j = 1; j * j <= num; j++) {
if (num % j == 0) {
if (check[j]) {
score[num] += -1;
score[j] += +1;
}
if (j * j != num) {
// 중근이 아닐 경우
if (check[num / j]) {
score[num] += -1;
score[num / j] += +1;
}
}
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(score[arr[i]]+" ");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 9763. 마을의 친밀도
문제 요약
- 마을의 좌표
- (x, y, z) 형태
- 마을 중 세 마을의 친밀도
- d12 + d13
- dij = abs(xi-xj) + abs(yi-yj) + abs(zi-zj)
- d12 + d13
시간 제한
- 1초
입력
- 마을의 수 N
- 3 ≤ N ≤ 1만
- N개의 줄에 마을의 위치 (x,y,z)가 주어짐
- -1000 ≤ x,y,z <+ 1000
출력
- 친밀도 중 가장 작은 값 출력
접근법
- 완전 탐색으로 생각하기
- 전체 마을 중 3개를 선택하는 모든 경우의 수에서 친밀도 계산하기
- 3중 for문 ⇒ 그러나 최악의 경우 100001000010000으로 시간초과
- ⇒ for문은 최대 2개까지만 사용 가능
- 전체 마을 중 3개를 선택하는 모든 경우의 수에서 친밀도 계산하기
- 최적화 하기
- x좌표 차이, y좌표 차이, z좌표 차이
- 우선 마을 좌표를 오름차순 정렬
- x좌표 우선 정렬
- x좌표 같으면 y좌표 정렬
- y좌표 같으면 z좌표 정렬
- 2중 for문을 사용해서 마을1, 마을2의 가장 작은 친밀도를 찾는다.
- 만약 더 작은 친구가 나오면 원래 저장해둔 친밀도는 d2에 저장하고 더 작은 친구는 d1에 저장한다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[][] town = new int[N + 1][3];
StringTokenizer st;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
town[i][0] = Integer.parseInt(st.nextToken());
town[i][1] = Integer.parseInt(st.nextToken());
town[i][2] = Integer.parseInt(st.nextToken());
}
int d1, d2, dist, answer = Integer.MAX_VALUE;
for (int i = 1; i <= N; i++) {
d1 = 10000;
d2 = 10000;
dist = 10000;
for (int j = 1; j <= N; j++) {
if(i != j){
dist = Math.abs(town[i][0]-town[j][0]) + Math.abs(town[i][1]-town[j][1]) + Math.abs(town[i][2]-town[j][2]);
if (d1 > dist) {
d2 = d1;
d1 = dist;
} else if (d2 > dist) {
d2 = dist;
}
}
}
answer = Math.min(answer, d1 + d2);
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기
문제 요약
- 정수 A가 B로 나누어떨이지면, B는 A의 약수이며 A는 B의 배수
- 최대공약수란 공통 약수 중 가장 큰 수
- N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것 찾기
- 이때 최대 공약수가 K의 약수면 안 됨
시간 제한
- 2초
입력
- 정수의 개수 N
- 4 ≤ N ≤ 100만
- N개의 수가 주어짐
- 20억을 넘지 않는 자연수
출력
- 정수 하나를 빼서 만들 수 있는 가장 큰 최대 공약수와 뺀 수를 공백을 두고 출력
- 없다면 -1
접근법
- 뽑는 숫자 위치 기준(i)으로 1~(i-1)까지 GCD와 (i+1)~N까지 GCD의 GCD를 구하고, K % GCD ≠ 0인 경우를 찾아서 최댓값으로 갱신한다.
- 이때, 미리 prefix, sufix 방향의 GCD를 기록한 배열을 만들고 사용하기(구간 → 점)
코드
import java.io.*;
import java.util.*;
public class Main {
static int getGCD(int a, int b) {
int tmp;
while (b != 0) {
tmp = a % b;
a = b;
b = tmp;
}
return a;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] prefix = new int[N + 1];
for (int i = 1; i <= N; i++) {
prefix[i] = getGCD(Math.max(prefix[i - 1], arr[i]), Math.min(prefix[i - 1], arr[i]));
}
int[] suffix = new int[N + 2];
for (int i = N; i >= 1; i--) {
suffix[i] = getGCD(Math.max(suffix[i + 1], arr[i]), Math.min(suffix[i + 1], arr[i]));
}
int k, gcd, ansGcd = -1, ansK = 0;
for (int i = 1; i <= N; i++) {
k = arr[i];
gcd = getGCD(Math.max(prefix[i - 1], suffix[i + 1]), Math.min(prefix[i - 1], suffix[i + 1]));
if (k % gcd != 0) {
ansGcd = Math.max(ansGcd, gcd);
ansK = k;
}
}
if (ansGcd != -1) {
bw.write(String.valueOf(ansGcd + " " + ansK));
} else {
bw.write(String.valueOf(ansGcd));
}
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 24523. 내 뒤에 나와 다른 수
문제 요약
- 길이가 N인 수열 A1~AN
- 1≤i≤N인 정수 i마다
- i<j≤N이고,
- Ai ≠ Aj인 정수 j중 최솟값 출력하기
- 없다면 -1 출력
시간 제한
- 1초
입력
- 수열 크기 N
- 1≤N≤100만
- Ai : 10억 ~ 10억
- 수열 A가 공백으로 구분되어 주어진다.
출력
- 각 i마다 조건을 만족하는 최솟값 j 출력
- 없다면 -1
접근법
- 완전탐색으로 접근하기
- 2중 for문으로 비교 ⇒ 하지만 N이 100만까지 이기때문에 for문을 한 번만 쓸 수 있다.
- 최적화하기
3 3 3 2 2 3 1 1 4 4 3 2 3 4- i = 1, start = 1, cnt = 1
- arr[i] == arr[i+1]이므로, cnt += 1
- i = 2, cnt = 2
- arr[i] == arr[i+1] 이므로, cnt += 1
- i = 3, cnt = 3
- arr[i] ≠ arr[i+1] 이므로, 인덱스 start부터 start+cnt-1까지 arr[i+1]을 기록해야한다.
- ⇒ 이 기록을 어떻게 해야 할까..?
- ⇒ imos 생각해보기
- i=1 → +(i+1)기록
- i=4 → -(i+1)기록
- … ⇒ N-1까지 진행하고 나서, 업데이트를 기록한 배열 구간합 진행 후 출력
- i = 1, start = 1, cnt = 1
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
long[] update = new long[N + 1];
int start = 0, cnt = 0;
for (int i = 1; i < N ; i++) {
if (cnt == 0) {
start = i;
cnt = 1;
}
if (arr[i] == arr[i + 1]) {
cnt++;
} else {
update[start] += i + 1;
update[start + cnt] += -(i + 1);
cnt = 0;
}
}
for (int i = 1; i <= N; i++) {
update[i] += update[i - 1];
if(update[i] == 0) update[i] = -1;
}
for (int i = 1; i <= N; i++) {
sb.append(update[i] + " ");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 23032. 서프라이즈~
문제 요약
- N명의 학생 1~N번 학번
- 먹고 싶은 스테이크 그램 조사
- 다음 조건에 따라 이벤트 진행
- 임의로 연속된 학번의 학생들 선택
- 임의로 대상 학생들을 두 그룹으로 나눔
- 그룹별로 학번이 인접해야 하며, 최소 1명 이상으로 구성
- 두 그룹의 무게 합 차 E 구하기(큰 - 작)
- E가 최솟값인 두 그룹이 당첨
- 여러 개가 있다면 스테이크 무게 합이 가장 큰 두 그룹 당첨
시간 제한
- 1초
입력
- N
- 2~2000
- 1번부터 N번 학생까지 적은 스테이크 무게 W
- 1≤W≤10000
출력
- 이벤트에 당첨된 학생들의 스테이크 무게 합 출력
접근법
- 완전 탐색으로 접근하기
- 2중 for문으로 대상 그룹 선정 (시작점, 끝점)
- for문을 이용해서 두 그룹을 구분할 기준점 선택
- ⇒ 3중 for문이므로 시간 초과 뜸 ⇒ 최대 2중 for문만 쓸 수 있다.
- for문을 이용해서 두 그룹을 구분할 기준점 선택
- 2중 for문으로 대상 그룹 선정 (시작점, 끝점)
- 최적화하기
- 합 ⇒ 누적합 배열로 미리 만들기
- 그룹 나누기
- 2중 for문으로 대상 그룹 선정
- 이분탐색으로 두 그룹으로 나눈다.
- group1 > group2
- e = mid - 1
- group1 ≤ group2
- s = mid + 1
- group1 > group2
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[] arr;
static int ansDiff = Integer.MAX_VALUE;
static int ansSum;
static void binarySearch(int s, int e) {
int mid, g1, g2, diff;
int start = s, end = e;
while (s <= e) {
mid = (s + e) / 2;
g1 = arr[mid] - arr[start - 1];
g2 = arr[end] - arr[mid];
diff = Math.abs(g1 - g2);
if(ansDiff > diff){
ansDiff = diff;
ansSum = g1 + g2;
} else if (ansDiff == diff) {
if(ansSum < g1 + g2) ansSum = g1 + g2;
}
if (g1 > g2) {
e = mid - 1;
} else {
s = mid + 1;
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= N - 1; i++) {
for (int j = i + 1; j <= N; j++) {
binarySearch(i, j);
}
}
bw.write(String.valueOf(ansSum));
bw.flush();
bw.close();
br.close();
}
}