본문 바로가기

Algorithm/Baekjoon38

11279_최대 힙 ▶실버 2 풀이 결론적으로 최댓값을 구하는 것이기 때문에 우선순위 큐를 이용한다. 연산 값이 0이며 우선순위 큐가 empty가 아닐 경우 pop, 연산 값이 양수일 경우 push 코드 #include #include #include #include #include #include using namespace std; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > x; if (x == 0) { if (pq.empty()) { cout 2023. 2. 3.
10799_쇠막대기 ▶실버2 문제 풀이 stack 이용 '()' => 레이저 제일 위에 있는 막대기는 ')' 가 나오기 전까지 레이저로 자를 수 있음 ※ 막대가 끊겨도 레이저를 쏘면 한 조각으로 치기 때문에 ')' 이 나온다고 해서 무작정 pop하면 안됨 즉, 1 : '('는 push 하고, 2 : ')'일 경우 레이저인지 쇠 막대기인지 확인 후 2-1: 쇠 막대기면 cnt(쇠 막대기의 오른쪽 끝 점 개수) 증가 2-2: 레이저이면 stack의 크기(쇠 막대기의 왼쪽 끝 점 개수)만큼 더한 후, cnt(쇠 막대기의 오른쪽 끝 점 개수) 만큼 pop해준 후 cnt 초기화 3: 반복문 다 돌린 후 마지막으로 cnt 더해 줌 코드 #include #include #include #include #include using name.. 2023. 2. 2.
17478_재귀함수가 뭔가요? ▶실버5 풀이 재귀함수 문제. 조건에 상관없이 재귀함수에서 항상 실행되는 문장은 "재귀함수가 뭔가요?" i 가 아직 n에 도달하지 않았을 때 실행될 문장은 "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." i가 n에 도달했을 때 실행될 문장은 "재귀함수는 자기 자신을 호출하는 함수라네" "라고 답변하였지." 마지막으로 재귀함수가 닫힌 후 실행될 문장은 "라고 답변하였지." 코드 #include #include #include #include using namespace std; void rec(.. 2023. 1. 22.
2156_포도주 시식 ▶실버1 풀이 연속으로 3잔을 마실 수 없으므로 2잔을 연속으로 마시면 한 잔은 쉬어야 하는데, 최대의 합을 내기 위해서는 연속 두 잔 이상을 마시지 않으면 안된다. 즉, 1번 잔을 마셨으면 꼭 2번 잔을 마시거나 3번 잔을 마셔야 한다. 2번과 3번을 모두 마시지 않으면 최대 값을 낼 수 없다. 이 점을 참고! 예제에서 5번째 잔까지만 표로 나타내면 6 10 13 9 8 여기서 모든 경우의 수는 (1, 2, 4, 5) (2, 3, 5) (1, 3, 4) 이다. ① (1, 2, 4, 5) => dp[2] + arr[4] + arr[5] ② (2, 3, 5) => dp[3] + arr[5] ③ (1, 3, 4) => dp[4] 이를 점화식으로 나타내면 dp[i] = max({ dp[i - 3] + arr[.. 2023. 1. 16.
9465_스티커 ▶실버1 풀이 여기서 중요하게 봐야할 것은 두 변을 공유하지 않는다는 점이다. 이 점을 참고하여 배열을 arr[i][j], dp[i][j] 두 개 만든다.(i는행, j는 열) ① n = 1이라면, 50 10 dp[0][0]의 값은 50이며, dp[1][0]의 값은 10이다. ② n = 2이라면, 50 10 30 50 dp[0][1]의 값은 dp[1][0] + arr[0][1] = 30 + 10 = 40 dp[1][1]의 값은 dp[0][0] + arr[1][1] = 50 + 50 = 100 이다. ③ n = 3이라면, 50 10 100 30 50 70 여기서부터 살짝 복잡해지는데, dp값이 두 가지 경우일 수 있다. dp[0][2]의 값은 dp[1][1], dp[1][0]의 값 중 큰 값에 arr[0][.. 2023. 1. 16.
1699_제곱수의 합 ▶실버2 풀이 ex) n = 12라면, ① dp[12 - 1*1] = dp[11], dp[12 - 2*2] = dp[8], dp[12 - 3*3] = dp[4] 중 가장 작은 값에 +1한 값이 dp[12]가 된다. 하지만 dp[1~11] 의 값을 알기 위해서는 1부터 1씩 증가하며 dp값을 구하는 작업을 먼저 진행한다. i = 1) dp[1] = 1 i = 2) dp[2]: dp[2 - 1*1] + 1= dp[1] + 1 = 2 i = 3) dp[3]: dp[3 - 1*1] + 1 = dp[2] + 1 = 3 ... 이런식으로 n까지 진행하는 과정에서, i 값에 따라 ①을 진행한다. 또, 주의할 점은 dp의 값을 dp값이 가질 수 있는 최대의 항의 수 개수로 초기화 해야한다. (dp[i] = i) 코드 .. 2023. 1. 13.

티스토리툴바