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

1일1알

백준 5557번 1학년 C++

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 2차원 dp 배열을 만든다. dp[i][j]는 i번째까지의 식의 결과가 j인 경우의 수이다. 처음에는 결과가 v[0] 하나만 존재하기 때문에 dp[0][v[0]] = 1로 초기값을 정해준다. i가 늘어날때마다 j를 0~20을 검사하면서 dp[i-1][j]가 0이 아니라면 i-1번째까지의 값이 j인 경우가 존재한다는 뜻이다. 여기서 j+v[i], j-v[i]를 계산해 0~20사이라면 전 결과..
알고리즘 2023. 4. 20. 10:46
백준 18353번 병사 배치하기 C++

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 가장 긴 증가하는 부분 수열 응용문제 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n;..
알고리즘 2023. 3. 22. 08:04
백준 1965번 상자넣기 C++

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 다이나믹 프로그래밍, 가장 긴 증가하는 부분 수열을 구하면 되는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long lo..
알고리즘 2023. 3. 21. 10:12
백준 4095번 최대 정사각형 C++

https://www.acmicpc.net/problem/4095 4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 현재 좌표가 1일때 왼쪽 위, 왼쪽, 위쪽 에서 가능한 정사각형 중 가장 작은 정사각형 + 1을 하면 현재 좌표에서 만들 수 있는 가장 큰 정사각형이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include..
알고리즘 2023. 3. 17. 11:08
백준 4097번 수익 C++

https://www.acmicpc.net/problem/4097 4097번: 수익 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10 www.acmicpc.net 전날 + 지금 수익이 지금 수익보다 크면 지금까지의 최대 수익을 갱신한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; u..
알고리즘 2023. 2. 13. 13:55
백준 14494번 다이나믹이 뭐에요? C++

https://www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다. www.acmicpc.net dp #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; const int divVal = 1000000007;..
알고리즘 2023. 2. 5. 11:54
이전 Prev 1 2 3 4 ··· 11 Next 다음