https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복&재귀 문제이다. 지금까지 풀었던 분할정복 문제 중에서는 쉬운 축에 속하는 것 같다. 재귀에 약해서 쫄았는데 생각보다 금방 풀렸다. 종이의 시작점의 행 번호, 열 번호, 종이의 크기를 매개변수로 보내 종이가 같은 수로 이루어져 있는지 확인한다. 종이가 같은 수로 이루어져 있으면, 해당 수의 카운터를 올리고 종료한다. 같은 수로 이루어져 있지 않으면, 재귀를 통해 크기를 1/3로 ..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 1단계에 해당하는 문제로 확실히 2단계 이상의 문제보다는 쉽게 금방 풀었다. 1. 0을 제외하고(알아볼 수 없는 번호) 일치하는 번호의 수를 구한다. 그리고 동시에 0의 개수를 구한다. 2. 0의 개수를 토대로 맞을 수 있는 번호의 최대 개수와 최저 개수를 구한다. (최대 개수는 0인 수를 모두 맞았을 경우이고, 최..

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

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를 선택했을 경우의 비용의 합과 ..