문제가 아주 지저분하고.. 불친절했다.. 그래서 지운이의 도움을 받아 풀 수 있었다.. 실버 3 치고는 정말.. 힘들었다..
https://www.acmicpc.net/problem/16131
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
0.5 초 (추가 시간 없음) 128 MB 1043 116 89 13.323%
문제
서울 S 과학고의 기숙사는 매우 특이한 체계를 가지기로 유명하다. 기숙사에는 수많은 방이 있고, 각각의 방에는 번호가 붙어져 있어 번호가 작을수록 더 좋은 질의 방을 갖게 된다. 이 기숙사의 운영부는 상점과 벌점이라는 것을 학생들에게 주지만, 어떤 과학고의 체계와는 달리 벌점 누적에 의한 퇴사 제도가 없다. 따라서 기숙사 운영부에서는 매주 각 학생의 상점과 벌점에 따라 학생들의 방을 재배정하게 된다. 1번 방과 가까운 최상의 방들은 상태가 매우 좋아 학생들이 바라지만, 끝번과 가까운 최하의 방들은 방의 상태가 처참해 학생들이 피하려고 한다.
기숙사 운영부는 처음 방 배정을 학번을 기반으로 배정하였는데, 학생들에게는 1번에서 N번의 학번이 주어지고 첫 주는 그 번호대로 방에 들어가게 된다. 1번인 홍 군과 홍 군의 친한 친구 조 군은 첫 주에 각각 1번 방과 A번 방에 배정되었다. 홍 군은 조 군과 같이 있기를 원했고, 두 학생의 방 번호의 차이가 B 이하이면 홍 군은 그 주에 기분이 좋아진다고 한다. 주어진 기간 M주 동안 학생들은 기숙사에서 지내게 되고, 마지막 주에는 상점과 벌점을 주지 않는다. 즉, M-1주 동안만 상점과 벌점을 기록한다.
M주 동안 홍 군의 기분이 좋은 주는 총 몇 주인지 알아내고, 홍 군이 최대 몇 주 동안 연속으로 기분이 좋은지도 알아내시오.
방의 교환
두 방의 교환이라는 것은, 2개의 방 각각의 사람을 서로 바꾸는 것을 의미한다.
방은 최고의 방에서 시작해서 최악의 방까지 순서대로 순위 상 인접한 두 방만 교환한다. 즉, 처음에 1, 2번 방을 확인하고, 다음에는 2, 3번, 마지막으로 N-1번과 N번 방의 상/벌점을 확인한다.
방의 교환 기준인 상, 벌점은 방을 바꾸기 전 주에 받은 것으로만 확인한다. 즉 상점과 벌점은 매주 초기화된다.
방의 교환 조건. 두 방의 교환이 일어나기 위한 조건은 다음과 같다. 이때, 점수는 상점-벌점의 값이다.
두 방의 학생의 점수가 모두 0 이상인 경우, 나쁜 방의 학생의 점수가 좋은 방의 학생의 점수보다 2점 이상 높다면 두 방을 교환한다.
좋은 방의 학생의 점수가 0 이상이고 나쁜 방의 학생의 점수가 음수이면 방을 바꾸지 않는다.
나쁜 방의 학생의 점수가 0 이상이고 좋은 방의 학생의 점수가 음수이면 방을 바꾼다.
두 방의 학생의 점수가 모두 음수인 경우, 나쁜 방의 학생의 점수가 좋은 방의 학생의 점수보다 4점 이상 높다면 두 방을 교환한다.
만약 방이 교체된다면, 방이 좋아진 사람에게는 -2점이, 나빠진 사람에게는 +2점이 부여되어 방 번호의 급격한 변동을 방지한다.
조건이 많고 까다롭다
그래서 풀 때 log를 다 찍어가며 푸는 것을 추천한다.
심지어 테케도 하나만 주어서 힘들었다..
많은 이들이 참고하길 바라며..
Python
def process_weeks(N, A, B, M):
# 초기 방 순서와 점수 초기화
seq = list(range(1, N + 1)) # 방 번호 순서
points = [0] * (N + 1) # 점수 배열
good_weeks = 0
current_consecutive_good = 0
max_consecutive_good = 0
for week in range(1, M + 1):
# 마지막 주에는 점수 입력을 받지 않음
if week != M:
merits = list(map(int, input().split()))
demerits = list(map(int, input().split()))
for i in range(1, N + 1):
points[i] = merits[i - 1] - demerits[i - 1]
# 홍 군과 조 군 위치 확인
Hong_pos = seq.index(1) + 1 # 방 번호는 1부터 시작하므로 +1
Jo_pos = seq.index(A) + 1
# 기분 좋은 주인지 확인
if abs(Hong_pos - Jo_pos) <= B:
good_weeks += 1
current_consecutive_good += 1
max_consecutive_good = max(max_consecutive_good, current_consecutive_good)
else:
current_consecutive_good = 0
# 방 교환 로직
for i in range(N - 1):
prev = points[seq[i]]
sub = points[seq[i + 1]]
if should_swap(prev, sub):
# 방 교환
seq[i], seq[i + 1] = seq[i + 1], seq[i]
# 점수 교환
points[seq[i]], points[seq[i + 1]] = sub - 2, prev + 2
return good_weeks, max_consecutive_good
def should_swap(prev, sub):
# Java의 조건과 동일하게 교환 조건 정의
if (prev >= 0 and sub >= 0 and sub - prev >= 2) or \
(prev < 0 and sub < 0 and sub - prev >= 4) or \
(sub >= 0 and prev < 0):
return True
return False
# 입력 처리
N, A, B, M = map(int, input().split())
# 결과 계산 및 출력
good_weeks, max_good_streak = process_weeks(N, A, B, M)
print(good_weeks, max_good_streak)
Java
import java.io.*;
import java.lang.*;
import java.util.StringTokenizer;
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();
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 전체 학생 수
int A = Integer.parseInt(st.nextToken()); // 조 군의 방 번호
int B = Integer.parseInt(st.nextToken()); // 기분 좋은 값
int M = Integer.parseInt(st.nextToken()); // 기숙사 생활 기간 (단위 -> 주)
int goodWeek = 0; // 기분 좋은 주
int seqWeek = 0; // 연속으로 기분 좋은 주
int MaxSeq = 0; // 연속으로 기분 좋았던 주 최대값
int[] point = new int[N + 1]; // 상벌점 (index 가 학번)
int[] seq = new int[N + 1]; // 현재 순서 (index 순서, value 학번)
for (int i = 1; i < N + 1; i++) {
seq[i] = i;
}
// 주의 수 만큼 반복
for (int week = 1; week <= M; week++) {
// 마지막 주가 아닌 경우 상점, 벌점 정산 -> 벌점은 빼기함
// 배열의 index 값은 방 번호
if (M != week) {
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
point[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
point[i] -= Integer.parseInt(st.nextToken());
}
}
int curA = 0; // 현재 조 군의 위치
int cur1 = 0; // 현재 홍 군의 위치
for(int i = 1; i<N+1; i++) {
if(seq[i] == 1) {
cur1 = i;
}
if(seq[i] == A) {
curA = i;
}
}
// A 학번 친구 순서랑 주인공 순서가 B 이하로 떨어졌다면 좋은 주
// 연속 주도 1 증가
if (Math.abs(curA - cur1) <= B) {
goodWeek++;
seqWeek++;
MaxSeq = Math.max(seqWeek, MaxSeq);
}
// 안 기쁘면 연속 기쁜 주 초기화
else {
seqWeek = 0;
}
for (int i = 1; i < N; i++) {
int prev = point[seq[i]];
int sub = point[seq[i + 1]];
// 교환 조건 확인 및 교환
if (change(prev, sub)) {
// 임시 변수로 point 값 저장
int tmpPrev = point[seq[i]];
int tmpSub = point[seq[i + 1]];
// 순서 교환
int tmp = seq[i];
seq[i] = seq[i + 1];
seq[i + 1] = tmp;
// 교환 후 point 값 갱신
point[seq[i]] = tmpSub - 2;
point[seq[i + 1]] = tmpPrev + 2;
}
}
}
System.out.println(goodWeek + " " + MaxSeq);
}
public static boolean change(int prev, int sub) {
// 둘 다 0 이상인경우 나쁜 방 친구가 2점 이상 높으면 교환
if (prev >= 0 && sub >= 0 && sub - prev >= 2) {
return true;
}
// 둘 다 음수인 경우 나쁜 방 친구가 4점 이상 높으면 교환
else if (prev < 0 && sub < 0 && sub - prev >= 4) {
return true;
}
// 나쁜 방 친구가 0 이상, 좋은 방 친구가 음수라면 그냥 교환
else if (sub >= 0 && prev < 0) {
return true;
}
else {
return false;
}
}
}이 문제는 지운이가 아니었으면 못풀었을 것.... 영광을 지운이에게 30% 정도 돌리겠습니다..
포스팅이 없길래 올리기!
