PS/BOJ57 백준 3172 / C++ https://www.acmicpc.net/problem/3172 3172번: 현주와 윤주의 재미있는 단어 게임 현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다. 두 단어 A와 B가 있을 때, A가 B www.acmicpc.net [ 풀이 ] 문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다. 이 인덱스를 문자열과 함께 묶어서 들고다니자. 이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자. 순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 다음에 보는 문자열의 인덱스가 현재보는.. 2022. 8. 4. 백준 1086 / C++ https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net [ 풀이 ] N이 작고 순열의 각 원소의 순서가 중요하므로 비트DP로 순회하자. p1 p2 .... pn 순으로 간다고 하자. p1에서 p2로 갈 때 수는 p1*10^(p2의 길이)+p2 가 된다. p2의 길이는 최대 50이므로 단순 계산으론 안되고 미리 10^m (modk)를 전처리해놓으면 된다. p_i들 또한 k로 나눈 나머지만 중요하므로 순회하면서 모두 k로 나눈 나머지로 전처리해놓자. 이제 dp식을 세우자. dp[bit][v]는 .. 2022. 8. 4. 백준 15678 / C++ https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net [ 풀이 ] dp[j]=max(0, dp[k])+a[j] 이다. (단, k>=j-D , k qe || e > D; for (int i = 1; i > K[i]; ll ans = K[1]; upd(1, 1, n, 1, K[1]); for (int i = 2; i 2022. 8. 2. 백준 3114 / C++ https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)까지 왔을 때 합의 최댓값이라 하자. dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]에서 올 수 있다. 앞의 두 경우는 이전dp값에다 현재 (i,j)에서 위아래로 바나나와 사과개수를 더해주면 된다. 이미 각 열에 대한 바나나의 합과 사과의 합을 전처리해놓자. dp[i][j-1]에서 오는 경우는 만약 (i,j)가 사과였다면.. 2022. 8. 2. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음