분류 전체보기

[11054] 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 💡 내 코드(C++) // [11054] 가장 긴 바이토닉 부분 수열 // https://www.acmicpc.net/problem/11054 // dp #include #include #define MAX 1001 using namespace std; void increase(); void decrease(); int bitonic(); int n, a[MAX] = { 0 }; int dp_inc[MAX], dp_..

[11053] 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 💡 내 코드(C++) // [11053] 가장 긴 증가하는 부분 수열 // https://www.acmicpc.net/problem/11053 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int cn..

[1120] 문자열

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 🔎 해결 방법 현재 순간에서 가장 최선의 경우만 고려하는 그리디 알고리즘의 특성을 이용하면 생각보다 코드도 짧고 간단한 문제였다. 예를 들어 A = "adaabc", B = "aababbc" 라면 먼저 (B[0], A[0]), (B[1], A[1]), (B[2], A[2]) ... 이런식으로 비교를 한 다음, 다른 경우에만 gap을 증가시켜 주면 된다. ..

[11051] 이항 계수 2

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 🔎 해결 방법 고등학교 확률과 통계에서 배웠던 파스칼의 삼각형 공식만 기억하고 있다면 매우매우 쉬운 문제이다. 1 > n >> k; dp[0][0] = 1; dp[0][1] = 0; for(int i = 1 ; i

[11048] 이동하기

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 🔎 해결 방법 (1, 1)에서부터 (n, m)까지 가면서 오른쪽, 대각선, 아래쪽 중 가장 큰 값을 더해나가면 되지 않을까? 그럼 dp가 필요없는데? 라고 생각했지만 이 문제를 dp로 풀어야 하는 이유가 있다. 만약의 미로가 위와 같이 주어졌다면, 현재 내 위치에서 갈 수 있는 칸 중 가장 최댓값만 취해서 이동한다면 위와 같이 되고, 이것은 dp가 아니라 그리디 알고리즘이라고 ..

[14501] 퇴사(C++)

🍃 문제 바로가기 🔎 해결 방법 처음에는 앞에서부터 계산을 하려고 했었다. 예를 들어, dp[n] 을 n일까지 상담을 했을 때 얻을 수 있는 최대 이익이라고 한다면 가능한 모든 경우를 조합해서 그 중 max 값을 찾아서 dp에 저장하려고 했는데 이렇게 하다보니 예외 처리 해줘야 할 것이 너무 많아서 결국 구글링의 도움을 받았다. 첫째날부터 계산을 해도 풀 수 있긴 하지만, 마지막 날 부터 계산을 한다면 코드도 간결하고 훨씬 더 간단하게 답을 도출할 수 있다! 만약 위와 같은 표가 주어졌다면, 1. dp[7] 7 + t[7] = 9 > 8 이므로 7일에 있는 상담은 할 수 없다. 따라서 dp[7] = dp[8] = 0 (dp[n + 1] = 0으로 사전에 초기화 해줘야 함) 2. dp[6] 6 + t[6]..

[4963] 섬의 개수(C++)

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..

[2512] 예산

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net 처음엔 코드도 60줄이 넘고 내가 생각하기에도 코드가 너무 복잡한 것 같은데 제출 결과도 계속 틀렸다고 떠서 뭐가 문제일까 생각해봤더니 예외 테스트케이스가 있었다... 이분 탐색 문제였기 때문에 자꾸만 어떤 표본들의 중간값을 찾으려고 했던 탓이다. 예를 들어, 각 지방에서 요청한 예산이 100, 110, 120, 130 ..