[BaekJoon] #16478 - 원의 분할 [Java][C++]
문제 링크 1. 아이디어 원에서 두 현이 교차하는 상황으로 방멱 정리를 활용하면 $p_{ab} \cdot p_{cd} = p_{bc} \cdot p_{da}$가 된다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...
문제 링크 1. 아이디어 원에서 두 현이 교차하는 상황으로 방멱 정리를 활용하면 $p_{ab} \cdot p_{cd} = p_{bc} \cdot p_{da}$가 된다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ ...
문제 링크 1. 아이디어 주어진 조건을 만족하는 이름을 출력하면 되는 문제로 건물 이름이 gwan으로 끝나야 하며 맨 앞 글자와 맨 뒤 글자가 같아야 해서 n으로 시작해야 한다. 중간에 k와 u를 적절히 넣으면 된다. 2. 복잡도 접근 시간 공간 풀...
문제 링크 1. 아이디어 시작 번호가 주어졌을 때 만들 수 있는 서로 다른 비밀번호의 개수를 구하는 문제로 DFS를 활용해서 해결할 수도 있지만 버튼이 $3 \times 3$ 크기라는 점에서 관찰을 통해서도 해결할 수 있다. 먼저 대칭성이 있으므로 코너 쪽에서 시작하는 경우, 코너 사이의 변에서 시작하는 경우, 중앙에서 시작하는 경우만 구하면...
문제 링크 1. 아이디어 콰트로치즈피자는 서로 다른 네 종류의 치즈 토핑이 들어가야 하며 치즈 토핑은 이름이 Cheese로 끝난다. 서로 다른 네 종류 이상의 치즈 토핑이 있는지 판단해야 하므로 집합 자료구조를 활용해서 이름이 Cheese로 끝나는 토핑들을 담은 후 집합의 크기가 4 이상인지 구하면 해결할 수 있다. 2. 복잡도 ...
문제 링크 1. 아이디어 주어진 조건을 보면 $P_1 = K$이므로 $P_{P_1} = P_K = P_2$다. 1부터 $N$까지 서로 다른 정수로 만들어지는 수열이려면 $K = 2$여야 한다. $P_2 = a$라고 두면 $P_{P_{P_1}} = P_{P_2} = P_a = P_3$이다. 1부터 $N$까지 서로 다른 정수로 만들어지는 수열이려...
문제 링크 1. 아이디어 주어진 격자에 대해 초기엔 모든 칸이 검은색이며 특정 위치를 흰색으로 바꾼 후 전파를 시작해서 전파가 끝났을 때 하얀 칸의 최대 개수와 해당 시간을 구하는 문제로 격자의 크기가 매우 커서 직접 전파를 하는 방식은 어렵다. 시작 칸의 행과 열은 따로 고를 수 있으므로 가로 방향과 세로 방향을 나눠서 생각할 수 있는데, ...
문제 링크 1. 아이디어 래환이가 최대한 늦게 다이어트를 시작하면서 목표 체중을 맞출 수 있는지 찾는 문제로 소개팅 날부터 역순으로 줄일 수 있는 체중을 더해나가서 가능한 순간 멈추면 가장 늦게 시작할 수 있다. 2. 복잡도 접근 시간 공간 풀이 ...
문제 링크 1. 아이디어 HG 표준음성기호로 암호화된 문자열을 원래 문자열로 복호화할 수 있는지 판단하는 문제로 주어진 문자열에서 현재 바라보는 인덱스를 기준으로 해당 문자로 만들 수 있는 코드로 현재 위치에서 시작하면 복호화가 가능하다는 점을 통해 해당 과정을 전체 문자열에 대해 반복하면 된다. 2. 복잡도 ...
문제 링크 1. 아이디어 주어진 수를 구성하는 숫자들의 순서를 변경해서 30의 배수가 될 수 있으면 주어진 수의 각 숫자들의 조합으로 가장 큰 수를 만들고 아니면 -1을 출력하는 문제로 30의 배수는 3의 배수이면서 10의 배수라는 점을 활용하면 해결할 수 있다. 3의 배수는 각 자릿수의 합이 3의 배수이면 3의 배수이고 10의 배수는 마지막...
문제 링크 1. 아이디어 $N$명이 마라톤에 참여하며 $N - 1$명이 완주했을 때 완주하지 못한 한 명을 찾는 문제로 동명이인이 있을 수 있어서 맵 자료구조를 활용해서 이름을 키, 인원을 값으로 설정해서 참여한 사람을 더하고 완주한 사람을 뺐다. 그러면 맵에서 값이 1인 사람이 유일하게 존재하게 되며 해당 사람이 완주하지 못한 사람이 된다....