목록알고리즘 문제 (35)

라이브러리는 도서관 아닌가요

백준 (BOJ) 17213 과일 서리 java dp

https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 중복 조합과 dp의 콜라보 N개의 자리를, N개를 뺀 M개(과일이 최소 하나씩 필요하므로)에 할당하는 문제. (n) H (m-n) = (n+(m-n)-1) C (m-n) = (m-1) C (m-n) = (m-1) C (n-1) 연산량을 줄이기 위해 계산 시작 전에 판별식을 넣었다. 채점 속도 차이는 없는 듯 하다. import java.io.BufferedReader; import java.io.IOEx..
알고리즘 문제 2022. 6. 10. 14:15
백준 (BOJ) 21317 징검다리 건너기 java dp

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 체감상 표기된 난이도 보다 훨씬 어려웠던 문제 =,.= 가지치기가 중요한 백트래킹 + dp이다. 1. 작은 점프로 분기 2. 큰 점프로 분기 3. 매우 큰 점프로 분기 dfs를 통해 세 가지 방식 모두로 분기하는 브루트 포스로 처음 방향을 잡고, dfs에서, 1. dp가 비어있다면(==0), 그대로 기대치 에너지 값으로 초기화 2-1. 비어 있지 않은 상황에서 기존에 저장된 값이 기대치 에너지 보다 작다면 후보군 제외 (return 종료) 2-2. 비어 있지 않은 상황에서 기대치 에너지가 더 작다면 후보가 될 수 있으므로 ..
알고리즘 문제 2022. 6. 8. 19:42
백준 (BOJ) 2705 팰린드롬 파티션 java dp

https://www.acmicpc.net/problem/2705 2705번: 팰린드롬 파티션 첫째 줄에 테스트 케이스의 개수 T(1 1 1 2 1 1 1 3 1 1 1 1 1 2 1 2 2 4 1 1 1 1 1 1 1 1 ( (8-0)/2 == 4 ) 1 2 1 1 2 1 ( (8-0)/2 == 4 ) 1 1 1 2 1 1 1 ( (8-2)/2 == 3 ) 3 2 3 ( (8-2)/2 == 3 ) 2 2 2 2 ( (8-0)/2 == 4 ) 1 1 4 1 1 ( 2 ) 2 4 2 ( 2 ) 4 4 ( (8-0)/2 == 4 ) 1 6 1 ( 1 ) 8 ( dp[0] ) import java.io.BufferedReader; import java.io..
알고리즘 문제 2022. 5. 10. 19:50
백준 (BOJ) 13023 ABCDE java dfs

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 비방문처리 시점을 찾는 게 중요했던 dfs 문제 시간 초과가 나지 않게끔 연결돼 있는 노드들만 따로 hashset에 저장해서 반복문을 돌렸다. 아 참고로, 연속된 노드 5개가 연결된 경로 4개가 존재하면 되는 문제이다. 1 - 2 - 3 - 4 - 5 답 1 - 2 - 3 - 4 - 1 답 1 - 2 - 3 - 4 오답 (문제가 논란의 소지가 다분히 있는 거 같은데... ABCDE인데 ABCDA가 가능하면 안 되는 거 아닌가?) 비방문 처리 시점은 아래의 경우를 생각해보면 된다. 1 - 3 - 4 (4..
알고리즘 문제 2022. 4. 29. 11:12
이전 Prev 1 ··· 3 4 5 6 7 8 9 Next 다음