출항사

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

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 약간의 테크닉이 필요한 다익스트라 응용 문제이다. 출발점 노드들이 주어지고, 산봉우리 노드들이 주어진다. 출발지 노드를 start라 하고, 산봉우리 노드를 end라고 하겠다. 우리가 구하고 싶은 값은 start -> end -> start로 탐색을 진행할때 지나온 간선의 가중치 최솟값이다. 여기서 약간만 생각하면 start -> end만 구해도 된다는 것을 눈치챌 수 있다. 굳이 end -> start를 탐색할 필요가 없기 때문이다. 그냥 start -> end에 도달하는 경로를 찾았다면 그 길을 따라서 그대..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한이 매우 널널해서 DFS로도 풀리는데 그냥 BFS가 더 간단해서 BFS로 풀었다. 구하고자 하는 것은 2차원 배열이 주어질때, 'P'의 거리가 2이하인 경우가 있는지 없는지이다. 따라서 'P'를 기준으로 탐색을 진행해서 거리 2 이내에 다른 'P'가 있는지 확인하면 된다. 주의해야 할것은 BFS를 돌릴때마다 방문 배열을 전부 밀어버려야 한다는 것이다. O(N^5)에 풀린다. import java.util.*; class Solution { private int[][] visited = new int[5][..