출항사

E - A Gift From the Stars AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 해석이 좀 어렵다. 트리가 주어지고, 여기서 star를 찾고자 하는 문제이다. 각 노드는 단 하나의 star에만 속할 수 있고, K - star는 star node와 연결된 노드의 개수로 결정이 된다. 그리고 Tree 형태로 주어지기 때문에 모든 노드는 star에 속할 수 밖에 없다. 문제를 위와같이 이해하면 DFS를 떠올려 볼 수 있다. 그리고 star 노드와 연결된 노드의 개수는 미리 O(N)으로 전처리 해놓을 수 있으..

D - Shift vs. CapsLock AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp Caps를 누른 상태인지에 따라 2가지 케이스로 나눌 수 있는데, 이를 활용하면 다이나믹 프로그래밍으로 풀 수 있는 문제이다. DP라는 것을 파악했다면 아주 간단하게 점화식을 세울 수 있는데, 이전 상태에 따라 caps가 켜졌는지, 꺼졌는지에 대해 2가지 케이스를 나누면 된다. 그리고 현재 입력해야 하는 문자열이 'A'인지 'a' 인지에 따라 최솟값을 갱신해 주면 된다. 약간의 함정은 꼭 z를 누르고 x를 눌러야 하는 것이 아니라는 ..