출항사

음.. C에서 조금 말려가지고 아쉽다. D도 조금 해매고.. E는 조금 신박했는데 왜 안뚫리는지 모르겠다. 그래도 문제는 전반적으로 재밌었던 것 같다. A - 4:32 N이 주어질때, 가장 가까운 5의 배수 숫자를 찾으면 된다. #include #include #include #include #include #include #define MINF 0x7f7f7f7f #define INF 300000000000001 #define MOD 10007 #define NUM 200010 #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; typedef pair pdd; typedef pair pi..

D - A Piece of Cake AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 당시에는 풀지 못했지만 좀 간단하게 생각해보면 어렵지 않은 문제이다. 딸기의 위치가 2차원 격자로 주어지고, 이 2차원 격자를 A개의 row, B개의 column으로 자르려고 한다. 그러면 (A+1) * (B+1)개의 공간이 생기게 되는데, 여기서 발생한 공간 중 딸기가 존재하는 최소 영역과 최대 영역을 구하면 되는 문제이다. 좌표의 크기가 매우 크기 때문에 좌표 압축이 필요하다는 것을 알 수 있고, 이 좌표 압축 기법을 활용하면 별도의 ..

A - 3:12 가장 어린 나이를 찾고, 시계방향으로 돌면서 이름을 출력하면 된다. #include #include #include #include #include #include #define MINF 0x7f7f7f7f #define INF 300000000000001 #define MOD 10007 #define NUM 200010 #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; typedef pair pdd; typedef pair pil; typedef pair piii; typedef pair piiii; typedef pair pll; typedef pair plll; ty..

C - Almost Equal AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 길이가 M인 문자열 N개가 주어진다. 우리가 해결해야 하는 문제는 이 문자열 N개를 랜덤하게 rearrange 했을때, i번째 문자열과 i+1번째 문자열의 차이가 1이 되게 만들 수 있는가?를 풀어야 한다. 아무리 단순하게 생각해봐도 이걸 해결하기 위한 알고리즘은 떠오르지가 않았다. 정렬로는 절대로 해결할 수 없고.. 전부 확인해야 하는것 아닌가?라는 생각이 들어 제한을 봤는데, N의 범위는 2이상 8이하로 주어진 것을 볼 수 있다. 그러면 문..

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를 눌러야 하는 것이 아니라는 ..