목록다이나믹 프로그래밍 (63)

1일1알

백준 1633번 최고의 팀 만들기 C++

3차원 dp배열을 만들어서 문제를 해결하였다. dp[k][i][j]의 의미는 k번 인덱스까지 i개의 백, j개의 흑을 뽑았을 때의 최대값 이다. 팀을 선택할 수 있는 경우는 백을 뽑는경우, 흑을 뽑는경우, 아무도 뽑지 않는 경우 셋으로 나눌 수 있다. 따라서 점화식은 dp[k][i][j] = max (dp[k - 1][i - 1][j] + k번의 백의 점수, dp[k - 1][i][j - 1] + k번의 흑의 점수, dp[k - 1][i][j]) 로 나타낼 수 있다. 처음에 cin.eof를 엉뚱한 곳에 넣어서 입력이 한개가 더 들어와서 헤맸다. 앞으로 주의해야겠다. #include #include #include #include #include #include #include #include #inclu..
알고리즘 2022. 2. 19. 18:04
백준 22857번 가장 긴 짝수 연속한 부분 수열(small) C++

포인터 두개 (start, end)를 이용해서 탐색을 하는데, start 인덱스의 원소가 짝수일 때만 검사하고, 홀수가 k+1 들어가있는 가장 작은 수열을 찾는다. ex) 수열 S가 1, 2, 3, 4, 5, 6, 7, 8, 9 이고 K가 2라면 처음 찾는 수열은 2, 3, 4, 5, 6, 7 일 것이다. 이 수열에서 짝수로만 이루어져있는 수열은 2, 4, 6 이고 길이는 end - start - (cnt - 1)로 구할 수 있다. cnt는 찾은 홀수의 개수이고 1을 cnt에서 빼주는 이유는 홀수를 k개가 아닌 k+1개를 찾았기 때문에 더 찾은 1개를 cnt에서 빼주는 것이다. 그리고 찾은 수열을 일단 유지하면서 start를 이동시키고 start 인덱스의 원소가 홀수면 cnt를 줄여준다. 두번째 경우는 ..
알고리즘 2022. 2. 18. 12:21
백준 1028번 다이아몬드 광산 C++

dp[행][열][방향] 3차원 dp배열을 만든다. 방향은 0, 1, 2, 3 순서로 왼쪽 위, 오른쪽 위, 오른쪽 아래, 왼쪽 아래이다. dp[행][열][방향] 에 들어가는 수는 (행, 열) 에서 [방향] 쪽으로 이어지는 1의 개수이다. 배열을 위에서 아래로 순회하면서 왼쪽 위, 오른쪽 위 즉 dp[행][열][0], dp[행][열][1] 을 그 전 좌표의 값 + 1로 채워주고 아래에서 위로 순회하면서 오른쪽 아래, 왼쪽 아래 즉 dp[행][열][2], dp[행][열][3] 을 그 전 좌표의 값 + 1로 채워주었다. 다시 배열을 순회하면서 아래로 뻗어지는 두 수 중 작은 값을 기준으로 밑으로 내려가서 밑에서 위로 올라가는 수 중 작은 값이 앞에서 구한 값보다 크거나 같으면 다이아몬드를 만들 수 있다. 이 ..
알고리즘 2022. 2. 17. 15:50
백준 1099번 알 수 없는 문장 C++

1. 문장을 순회하면서 각각의 단어마다 현재 인덱스 - 단어의 크기 + 1 부터 현재 인덱스까지의 구성된 문자가 단어와 같은지 확인한다. ex) 현재 인덱스가 2이고, 단어가 "one" 이라고 하면 2 - 3 + 1 = 0 부터 2 까지 구성된 문자는 n, e, o 이고 이는 "one"과 구성된 문자가 같다. 2. 1에서 구한 인덱스 - 단어의 크기 + 1 이 0보다 작거나 구성된 문자가 같지 않다면 다음 문자를 검색한다. 1에서 구성된 문자가 같다면 순서를 바꾸는 비용을 구하고 dp로 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #incl..
알고리즘 2022. 2. 16. 13:52
백준 2296번 건물짓기 C++

1. 건물들을 x좌표 오름차순으로 정렬한다. 2. 좌표가 대각선 위로 올라가는 건물들과 대각선 아래로 내려가는 건물들의 이익을 따로 구하고 이익이 최대가 되는 경우를 구한다. 순열 문제와 비슷하게 푼 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; struct Building { int x; int y; int c; }; bool compare(const Building& lhs, const Building& rhs) { return lhs.x..
알고리즘 2022. 2. 15. 11:38
백준 2418번 단어 격자 C++

1. 3차원 dp 배열을 만든다. dp[ 행 ] [ 열 ] [ 문자열 크기 ] 2. 문자열의 0번 원소와 같은 행과 열의 dp [ 행 ][ 열 ][0] 을 1로 설정한다. 3. k를 1부터 문자열 크기 - 1 까지순회하면서 k번째 원소와 같고 주변에 k-1번째 원소가 있다면 dp[i][j][k]에 dp[주변 행][주변 열][k - 1]을 더해준다. 4. 모든 dp[행][열][문자열 크기 - 1]을 더한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; ..
알고리즘 2022. 2. 14. 11:15
이전 Prev 1 ··· 3 4 5 6 7 8 9 ··· 11 Next 다음