https://www.acmicpc.net/problem/27728 27728번: 개구리와 쿼리 $N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리들이 모여있다. 각 개구리들은 초기 위치 $\left(S_{x},S_{y}\right)$에서 배열의 오른쪽 끝$\left(X,N+1\right)$에 있는 육지에 도착해야 한 www.acmicpc.net 문제는 누가봐도 dp + 누적 합으로 해결하는 문제이다. 나도 처음에는 간단하다고 생각했는데, 막상 머릿속으로 시간을 계산해보니까 x좌표 N개, y좌표 N개, 개구리 Q마리 ->O(N^2*Q)가 걸렸다. 이는 당연히 시간초과이고, 시간을 줄일 방법을 찾아야했다. 먼저 dp[i][j]에 dp[i][n]까지 가기 위해 남은 시간을 저..
PS
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 처음에는 상당히 애를 먹었던 문제 처음에 접근했던 방식은 (+) 연산자나 (-) 연산자는 (*) 연산자와 (/) 연산자보다 우선순위가 밀리기때문에 바로바로 출력하지 않고 뒤에 나오는 연산자를 기다리다가 출력을 하는 형식으로, (*)연산자와 (/)연산자는 우선순위는 높지만 뒤에 또 (*)연산자나 (/)연산자가 나오게 된다면 연속적으로 이루어지기에 역시 저장을 한 후 출력을 하는 형식으로, 괄호가..
https://www.acmicpc.net/problem/27725 27725번: 지수를 더하자 서로 다른 $N$개의 소수로 이루어진 집합 $P=\{p_{1}, p_{2}, \cdots, p_{N}\}$이 있다. 양의 정수 $i$에 대하여 $\frac{i}{p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times \cdots \times p_{N}^{a_{N}}}$의 값이 양의 정수가 되도록 하는 www.acmicpc.net 문제가 너무 어렵게 생겨서 지레 겁을 먹었던 문제 그런데 읽다보니 그냥 소인수분해를 이용한 문제 풀이라는 것을 알고 나름 간단하게 해결했다. 다만 문제 조건 K > n; ll k, y, ans=0; for(int i=0; i> x; v.push_back(x); } ci..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 그야말로 빡구현.. 3시간 풀로 집중하고 노트 열심히 써가면서 구현했다 처음에는 별 것 없다고 생각했는데, 의외로 벽을 튕기고 나온 상어를 구현하기가 까다로웠다. 나머지 연산을 이용해서 상어의 위치를 업데이트 해주려 했으나, 상어가 양수 방향으로 이동할 때는 별 문제가 없었지만 상어가 음수 방향으로 이동할 때 과부하가 걸려서 엄청 헤맸던 문제 그리고 구현하고 보니까 같은 공간에..
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 비트연산자를 공부한 후 가장 처음 도전한 문제 배우고 응용은 처음이라그런지 상당히 코드는 더럽지만 그래도 어느정도 알겠다.. 계속 틀린 이유는 k보다 v.size()가 작은 경우를 고려하지 않아서 틀렸고, 16번째 줄 구현이 너무 어려웠다. 내 생각에는 (1
