알고리즘 문제풀이58 [백준 1463] 1로 만들기 [문제 바로가기]👇 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 1. 테이블 정의 dp[n] : 정수 n을 1로 만드는데 사용하는 연산 횟수의 최솟값 2. 규칙 찾기 정수 n이 할 수 있는 연산의 종류(나누기 3, 나누기 2, 빼기 1) 중 가장 작은 연산 횟수를 가진 걸 찾아야 함 정수 n이 가능한 연산을 모두 해 각각의 연산값 중 최소를 가지는 거 찾기 i가 3으로 나누어 떨어진다면 dp[i] = dp[i/3]의 값(i/3을 1로 만드는데 필요한 연산 횟수의 최솟값)에 3으로 나누는 연산 한 번더 추가한 값 i가 2으로 나누어 떨어진다면 dp[i] = dp[i/2]의 값(i/2를 1로 만드는데 필요한 연산 횟수.. 2023. 3. 28. [백준 11727] 2xn 타일링 2 [문제 바로가기]👇 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 1. 테이블 정의 dp[n] = 2*n 타일을 채우는 방법의 수 이라고 테이블을 정의한 다음 타일을 채우는 규칙을 찾았다 2. 규칙 찾기(점화식 찾기) 타일은 1x2, 2x1, 2x2 총 3가지의 종류가 있다. 만약 맨 마지막에 2x1 타일을 놓아서 2xn 타일을 모두 채웠다고 한다면 2x1 타일 앞에는 n-1개가 남게 된다. 이 n-1의 공간을 채우는 방법의 수는 위에서 정의한 테이블에 따르면 dp[n-1]에 저장되어 있다. 그렇다면 맨 마지막에 1x2 타일을 놓아서.. 2023. 3. 28. [백준 1149] RGB거리 [문제 바로가기]👇 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 현재 집이 옆집의 색과 같으면 안된다는 규칙이 있어서 각 집을 RGB색으로 각각 칠했을 때의 비용을 모두 저장해서 비교를 했다 규칙 찾기 현재 집이 이전 집과 색이 다르다면 집을 칠하는 규칙을 만족하기 때문에 이전 집, 다음 집 모두가 아니라 이전 집과만 색 비교를 해도 가능 현재 집이 R색을 칠했다면, 이전 집은 G,B색 중 최솟값을 칠한 비용 + 현재 집이 R색을 칠했을 때 비용 현재 집이 G색을 칠했다면, 이전.. 2023. 3. 28. [백준 1541] 잃어버린 괄호 [문제 바로가기]👇 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 💡풀이💡 식이 주어졌을 때 최소의 값을 만들기 >> 가장 작은 수 - 가장 큰 수 를 만들면 되지 않을까??? 하는 생각으로 접근 식에 여러 숫자와 여러 연산자가 있겠지만 가장 간단한 형태로 생각해보면 마이너스 연산자(-)를 기준으로 가장 작은 수와 가장 큰 수가 나뉘게 된다. 마이너스 연산자 + 1만큼의 수의 덩어리가 생기게 됨 마이너스가 나오기 전까지 앞의 숫자들을 모두 계산해서 하나의 수 덩어리를 만들고 마이너스가 나온 이후의 숫자.. 2023. 3. 7. [백준 2146] 다리 만들기 [문제 바로가기]👇 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 💡풀이💡 한 섬에서 다른 섬으로 최소의 거리를 가진 다리 놓기! 출발하는 섬과 도착하는 섬이 달라야 하고, 이를 판단할 수 있어야 함! >> 섬 별로 번호 붙이기 한 섬에서 출발해서 다른 섬까지 도착하는 최소 거리 재기 >> BFS로 최소 찾기 1. 입력 받기 static int[] dr = {-1,0,1,0}; // 상우하좌 static int[] dc = {0,1,0,-1}; // 상우하좌 static int N, min; static bool.. 2023. 2. 28. [백준 17471] 게리 맨더링 [문제 바로가기]👇 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 💡풀이💡 문제에서 알 수 있는 정보 1~N개의 구역을 두 개의 선거구로 나누기 두 개의 선거구는 최소 구역을 하나 포함 && 모두 연결되어 있어야 함 > 두 개의 선거구 내 구역을 수가 동일할 필요 x >> 공집합과 전체집합을 제외한 나머지 부분집합! 중에서 각 선거구 내 구역이 모두 연결되어 있으면 만족! 전체 흐름 부분집합 완성 각 선거구가 조건에 맞는지 확인 && 각 구역의 인구수 합 찾기 선거구 조건에 맞으면 최솟값 구하기 1. 입력 받기 그래프가 1번부터 .. 2023. 2. 26. 이전 1 2 3 4 5 6 7 ··· 10 다음
