https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 이분탐색 문제이다. 처음에 이게 왜 이분탐색 알고리즘 문제인지 감이 안 잡혔지만.. 1씩 더해가면서 승률이 바뀌는지 안바뀌는지 확인을 한다면, X Y가 클 경우 많은 시간이 걸릴 것이라는 생각이 들었다. 이분탐색 알고리즘을 사용하여 반씩 범위들을 좁혀가며 찾으면 효율적일 것이다. 탐색하는 수를 '게임을 몇 판 더 해야하는지'로 둔다. 그리고 그 수로 승률(Z)를 구한다. Z가 바뀌지않았으면..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색 알고리즘을 사용하는 문제이다. 이전에 프로그래머스에서 '입국심사' 문제를 풀었던 것이 도움이 되었다. https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 주어진 배열에서 연속해서 3개까지 선택할 수 없고 최댓값을 구하는 문제로 이전에 풀었던 계단오르기(https://www.acmicpc.net/problem/2579)와 비슷한 문제이다. 계단오르기에서는 도착 지점을 무조건 선택해야 하지만 포도주 시식에서는 상관 없다. 그래서 선택하지 않는 경우를 추가하며 경우의 수가 하나 더 늘었다. 초기값 (n = 1, n= 2) dp[1] = glass[1] d..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 상향식 or 하향식으로 푸는 DP 개념을 안다면 금방 쉽게 풀린다. cost 배열과 크기가 같은 2차원의 dp 배열에 dp[i][j]까지의 비용의 합을 저장한다. 1. dp 배열의 0행 : 1번 집의 R, G, B 값을 저장한다. 2. dp 배열의 1 ~ N-1행 - R을 선택할 경우 : 현재의 행에서 R을 선택할 경우의 비용에 이전 행에서 G를 선택했을 경우의 비용의 합과 ..