문제 : boj15738
풀이 첫 줄에 강력한 스포가 있다. 혹시 아직 못 풀어서 이걸 어떻게 풀지? 생각되어 풀이를 봤다면, 이하 풀이를 보면 많이 짜증날 수 있으니 다시 한번 문제를 잘 읽어보고 직접 도전해보는걸 추천한다.
-------
풀이 : 애초에 배열 A가 아무런 의미가 없다 ㅋㅋㅋ 그냥 입력받은 n과 k만 가지고 각 m개의 연산에 따라 사칙연산으로 k의 위치만 바꿔주면 된다.
A. i가 양수일 때 i < k 라면 무시하면 된다. -> 그리고 i-k+1로 k를 변경해주면 된다.
B. i가 음수일 때 n+i+1 까지 영향을 끼치므로, 그보다 k가 작다면 무시하면 된다. -> 그리고 2*n-k+i+1로 k를 변경해주면 된다!
따라서 시간복잡도는 O(M)이다. N은 아무런 영향을 끼치지 않는다. 이하 코드에서도 배열 A는 그냥 무시해버린다. 이 문제를 해결하는데 아무런 의미도 없는 정보이기 때문이다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private void solution() throws Exception {
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 m = Integer.parseInt(st.nextToken());
br.readLine(); // throw
while (m-->0) {
int i = Integer.parseInt(br.readLine());
if (i > 0 && i < k) continue;
if (i < 0 && n+i+1 > k) continue;
k = i>0 ? i-k+1 : 2*n-k+i+1;
}
System.out.println(k);
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
[자바] 백준 9842 - Prime (0) | 2022.04.22 |
---|---|
백준 11008 자바 - 복붙의 달인 (boj 11008 java) (0) | 2022.04.21 |
백준 1940 자바 - 주몽 (boj 1940 java) (0) | 2022.04.19 |
백준 17550 자바 - Inquiry I (boj 17550 java) (0) | 2022.04.18 |
백준 17359 자바 - 전구 길만 걷자 (boj 17359 java) (0) | 2022.04.17 |
댓글