ps
-
[PS] 백준 2293번: 동전 1, 2294번: 동전 2카테고리 없음 2023. 11. 30. 22:26
동전 1 동전 2 dp연습하며 고른 문제이다. 무엇을 기준으로 dp를 할까 엄청 고민하다 결국 힌트를 봐버렸다. 총 가격으로 dp를 한다는 아이디어를 얻자마자 쉽게 풀 수 있었다. dp는 언제쯤 익숙해질까... 이런식으로 n원을 내기 위한 총 경우의 수를 계산하면 된다. 동전2는 저기서 경우의수가 대신 n원당 내야하는 동전의 수로 업데이트 하도록 바꿔 쉽게 연계해서 풀었다. // 동전 1 #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int n, k; vector coins; int dp[1000..
-
[PS] 백준 1260번: DFS와 BFS문제해결 2023. 11. 30. 16:27
DFS와 BFS 너무 정직한 DFS, BFS 문제이다. 다만, 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 이 부분 참고하여, DFS, BFS할 때 FIFO, LIFO에 맞춰 저렇게 sort 해준 뒤 push_back 해주면 끝. #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int N, M, V; vector av[1000]; bool visited[1000]; void dfs() { memset(visited, 0, sizeof(bool) * 1000..
-
[PS] 백준 9251번: LCS, 백준 5582번: 공통 부분 문자열문제해결 2023. 11. 20. 19:57
LCS, 공통 부분 문자열 dp는 할때마다 어려운 것 같다. O(N) dp에 좀 적응했다 싶었는데 O(N²) dp가 나와서 애먹었는데, 이번엔 2차원 dp다. 이런식으로 dp를 진행하면 된다. // 9251번: LCS #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i > s1 >> s2; if (s2.length() > s1.length()) swap(s1, s2); FOR(i, s1.length()) { ..
-
[PS] 백준 11689번: GCD(n, k) = 1문제해결 2023. 11. 20. 14:44
GCD(n, k) = 1 1'000'000까지의 소수를 모두 만들고, 소인수분해 한 후 오일러 곱 공식을 이용해서 풀려고 했다. 하지만 반례를 못찾아서 계속 끙끙대다 결국 답지를 열어버렸다. 반례는, 소인수분해를 했을 때, 소인수가 p, q, r, s일 경우 $ans = n\times \left ( 1-\frac{1}{p} \right )\times \left ( 1-\frac{1}{q} \right )\times \left ( 1-\frac{1}{r} \right )\times \left ( 1-\frac{1}{s} \right )$ 이 답이 되는데, s가 만약 1'000'000보다 큰 수라면, 해당 연산에 포함되지 못해 생기는 문제였다. 남은 s를 소인수에 추가해서 해결했다. 저번에도 정확히 같은 문..
-
[PS] 백준 1882번: 분수 찾기, 30449번: Reafy 수열문제해결 2023. 11. 7. 23:59
분수 찾기 Reafy 수열 이 링크 참고해서 어거지로 풀었다. 요약하자면, 이런식으로 a/b, c/d를 알 때 다음항인 p/q를 알 수 있다는 뜻이다. 이걸로 Reafy 수열은 간단하게 해결. 근데 이걸로 분수 찾기를 하려고 하니 너무 당연하게도 시간초과가 났다. Reafy 수열의 다른사람들 코드를 보니깐 int find_pos(int a, int b) { int ret = 0; for(int i = 1; i > K; int a = 0, b = 1, c = 1, d = N; if (K == 1) { cout
-
[PS] 백준 16455번: K번째 수 찾는 함수문제해결 2023. 11. 1. 20:55
K번째 수 찾는 함수 Reafy 수열 이 문제를 풀어보려고 이것저것 찾다가 16455번까지 오게되었다. 결국 저건 카운팅 소트로 했지만... quick selection이라는 알고리즘이 존재한다더라. 이를 이용해서 빠른 시간 이내에 k번째 수를 찾는게 정답. quick selection을 대충 조사해보니 일종의 이진탐색과 비슷해보이는데 우선 아무거나 하나를 골라서, 그 수보다 작은건 왼쪽, 큰건 오른쪽에 몰아넣으며 탐색공간을 줄여나가는 것이다. 위 그림의 4번, 5번 과정 if (pivval < a[lidx] && a[ridx] < pivval) { swap(a[lidx], a[ridx]); lidx++, ridx--; } 코드로는 위 부분에서 조건을 if (pivval
-
[PS] 백준 30446번: 회문수문제해결 2023. 10. 28. 20:53
속으로 '되게 어려운데 이게 왜 실버지' 하고 꾸역꾸역 풀어서 맞췄다. 523456789의 숫자가 나오면 우선 1~9 : 9개 10~99 : 9개 100~999 : 90개 ... 이런식으로 다 더해서 99999999까지 다 처리해두고 100000000부터 523456789까지를 셈한다 그럼 여기서도 100000000부터 499999999까지는 4 * 90000 / 9이니 이만큼 더해주고 이런식으로 가운데숫자(홀수면 한자리, 짝수면 두자리)만 제외하고 남기고 다 처리해준다. 5234 5 6789. 왼쪽을 뒤집은 4325보다 오른쪽의 6789가 더 크면 추가로 5를 더해주고 만약 숫자가 523453215라 5234 5 3215 이렇게 오른쪽이 더 작으면 추가로 4만 더해준다... 암튼 이런식으로 꾸역꾸역 해..
-
[PS] 백준 2749번: 피보나치 수 3 / 11444번: 피보나치 수 6문제해결 2023. 10. 26. 20:06
피보나치 수 3 피보나치 수 6 인풋이 100경이다보니깐 O(N)으로만 해도 분명히 타임아웃이 날거라고 생각했다. 100경을 다 훑을순 없고, 100만으로 나눈 나머지만 출력하라니 대충 규칙이 있겠거니 싶었다. 여러가지 숫자로 실험하며 확인해보니 어떤 숫자 M으로 나눈 나머지로 피보나치를 하면 M - 1, 1, 0, 1, 1, 2, 3, ... 이런 구간이 존재하는 듯 했다. 미리 "M - 1, 1"이 나올때까지의 피보나치 수열을 만들어 두고 Fibonacci[N % 주기]를 출력하면 끝. 끝인줄 알았는데 0ms안에 끝나는 다른 사람들 답을 보고 답을 찾아봤다. 피보나치 수를 구하는 여러가지 방법 $\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = ..