https://www.acmicpc.net/problem/2737 2737번: 연속 합 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. www.acmicpc.net 연속되는 자연수의 합으로 해당 정수를 표현할 수 있는지 묻는 문제 당연히 임의의 자연수를 i라고 하면, 연속하는 자연수이므로 i + 1, i + 2, ... 와 같이 연속된 자연수의 합으로 정수 N을 표현해야 한다. 먼저 자연수 2 개로 N을 표현할 수 있는지 생각해보면, 연속이 시작되는 자연수 (가장 작은 자연수)를 i라고 가정하고, i + (i + 1) == N이 되어야 하므로 ( N - 1 ) % 2i == 0 이 되어야 한다. 또한, ..
PS/BOJ
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]까지 가기 위해 남은 시간을 저..
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시간 풀로 집중하고 노트 열심히 써가면서 구현했다 처음에는 별 것 없다고 생각했는데, 의외로 벽을 튕기고 나온 상어를 구현하기가 까다로웠다. 나머지 연산을 이용해서 상어의 위치를 업데이트 해주려 했으나, 상어가 양수 방향으로 이동할 때는 별 문제가 없었지만 상어가 음수 방향으로 이동할 때 과부하가 걸려서 엄청 헤맸던 문제 그리고 구현하고 보니까 같은 공간에..
