[99club/TIL] 5주차 - 수요일 TIL(Today I Learned)

안녕하세요. delay100 입니다. 

오늘은 99club 모의고사를 신청해서 18시부터 22시까지 java- 2팀으로 참가했습니다. 

문제에서 총 3문제가 나왔고, 2번 문제만 해결하였습니다..ㅠㅠ

해당 코드는 팀코드로 채택되어 기뻤습니다..!

java-2팀으로 참가했습니다

---

1번 문제. 스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

해결 못했습니다..

// 1번 피드백
dp의 핵심 -> 반복이 있느냐?
어느정도 작은 유형이 반복되는 경우(dp 확률이 up)
반복된 내용 -> 점화식 생성(계속 계산x)
dp 기본문제
1. https://www.acmicpc.net/problem/1003
2. https://www.acmicpc.net/problem/2839
쪼개서 최소 1~3까지 규칙o -> dp, 규칙x -> 그리디

---

2번 문제. 스카이라인 쉬운거

https://www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

import java.io.*;
import java.util.*;

// 2번
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());
		Stack<Integer> stk = new Stack<Integer>();
		int cnt = 0;
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()); // 실질적 사용X
			int y = Integer.parseInt(st.nextToken());
			
			// 스택이 비어있지 않고, 스택에서 꺼낸 값(스택의 상단 값)이 현재 값보다 큰 경우
			// 즉, 현재 위치보다 앞에 건물이 존재하고, 앞 건물이 현재 건물보다 더 큰 경우
			while(!stk.isEmpty() && (stk.peek() > y)) { 
				stk.pop(); // 스택에서 제거(앞의 큰 건물 제거)
				cnt++; // 정답 값(건물 수) +1
			}
			
			// (a)스택이 비어있고, (b)스택의 상단 값이 현재 값보다 작은 경우  
			// 즉, (a)위에서 정산된 건물을 제외했을 때, 현재 위치보다 앞에 건물이 없고 땅이 아니라 건물인 경우
			// 또는 (b)앞 건물이 현재 건물보다 더 작은 경우
			if((stk.isEmpty() && y > 0) || (!stk.isEmpty() && (stk.peek() < y))) {
				stk.push(y); // 스택에 건물 추가
			}
			
		}
		
		// 스택에 값이 남아있는 경우(세지 않은 건물이 남아있는 경우)
		// 예를 들어, 건물의 y좌표가 1, 2, 3으로 주어진 경우 위에서는 push만 됨
		while(!stk.isEmpty()) {
			stk.pop(); // 건물을 제거하면서
			cnt++; // 정답 값(건물 수) +1
		}
		
		bw.write(Integer.toString(cnt));
		
		br.close();
		bw.close();
	}
}

---

3번 문제. 중량제한

https://www.acmicpc.net/problem/1939

1939번: 중량제한

이분탐색 + BFS/DFS으로 풀이

---

감사합니다. 피드백 환영합니다.

풀지 못한 문제는 이번주 중으로 풀어볼 예정입니다..!