PS/BOJ57 백준 1493 / C++ https://www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net [ 풀이 ] 큐브들은 모두 작은걸로 큰걸 채울 수 있다. 따라서 그리디하게 길이에 맞는 가장 큰 큐브부터 사용하면 된다. (각 큐브가 작은것으로 큰걸 채우지 못하면 그리디를 사용할 수 없다.) 큐브를 사용했다면 박스는 세 부분으로 나뉜다. 이제 이 세부분으로 divide&conquer 해주면 된다. [ Code ] #include using namespace st.. 2022. 8. 12. 백준 11616 / C++ https://www.acmicpc.net/problem/11616 11616번: Digit Division We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m. Find the number of different suc www.acmicpc.net [ 풀이 ] 우선 짚고갈 것은 전체수가 m의 배수가 아니라면 m의 배수인 여러부분으로 분할할 수 없다. 이제 전체수.. 2022. 8. 12. 백준 12911 / C++ https://www.acmicpc.net/problem/12911 12911번: 좋아하는 배열 첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] dp[i][j]를 길이 i이고 j로 끝나는 조건을 만족하는 개수라고 하자. 전체 경우의 수는 dp[N][1]+...+dp[N][K]가 된다. 문제조건의 여사건은 A가 B의 배수라는 것이다. 즉, 뒤로갈수록 앞의 약수가 되면 된다. WLOG 순서를 뒤집어서 뒤로 갈수록 앞의 배수가 되도록 해도 된다. dp[i+1][j]=dp[i][1]+....+dp[i][k]-sum(dp[i][u]) (u는 j의 배수) 임을 알 수 있다. S(i)=dp[i][1]+...+dp[i][k]라고 정.. 2022. 8. 12. 백준 25112 / C++ https://www.acmicpc.net/problem/25112 25112번: Single-track railway The first line specifies the number of stations, $n$. In the second line, $n - 1$ numbers are given, corresponding to the initial travel times between the adjacent stations (the $i$-th number is the travel time between stations $i$ and $i + 1$). The third www.acmicpc.net [ 풀이 ] 매번 업데이트하면서 min(S[n]-2*S[i])를 찾아주는 문제이다. 펜윅트리로 업데이트해주.. 2022. 8. 12. 이전 1 2 3 4 5 6 7 8 ··· 15 다음