문제링크 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 문제 자체의 이해는 어렵지 않은데 구현이 어려운 케이스 풀이 삭제해야할 인덱스를 ArrayList에 담았다. 그리고 ArrayList 에 있는지 없는지 확인하여 없으면 StringBuilder 에 append 하도록 했는데 구현이 복잡했다. import java.io.*; import java.math.BigInteger; import java.util.*; public class Main { static Buffered..
🧩Algorithm
문제 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net dp 의 냄새는 나지만 어떻게 풀어야될지 몰라서 틀린 문제입니다. dp 는 익숙해지는게 어려운 주제인거 같지만 그래도 공부하면 할수록 보이는거 같습니다. 이 문제의 핵심은 knapsack 0-1 입니다. 해당 개념을 모르신다면 백준 12865를 꼭 풀어보시고 풀이를 확인해보시길 바랍니다. 2023.07.04 - [Algorithm🧩] - 백준 12865 평범한 배낭 (0-1 knapsack) 💡풀이 knapsack 1-0 를 떠올려야하는 이유는 구슬을 쓸 수..
참고 중요한건 왜 dp인지 이해하는 것 dp[w][k] : 가방의 최대 무게가 w이고 k 번째 보석을 담을 때 갖을 수 있는 가치 최댓값 _(그림 오타 dp[3][k+1] -> dp[3][k]) 예를 들어, 최대 무게가 6kg 이고 k번째 보석을 담은 상태라고 하자. 다음 보석을 담을 때의 점화식을 세워보자. (dp[6][k+1]) 그렇다면 k+1 번째 보석을 담을 수 있다면 담는다 or 안담는다 로 나눌 수 있다. 이때 안 담는다면 최대 무게가 6kg 이고 k 번째 보석을 담는 상태와 같다. 따라서 dp[6][k+1] = dp[6][k] 반대로 담는다면 dynamic programming 의 본질에 맞게 subproblem으로 쪼갤 수 있다. k+1 번째 보석이 3kg 이다. 그렇다면 우리는 가방 최대..
