[Java] BaekJoon 3678. 성냥개비 (골드2) (DP)

문제출처: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 문제이해 목표 성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오. 주의: 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 풀이 1. 주어진 성냥개비를 모두 사용해 만들 수 있는 작은 수 구하기 결론: DP로 풀이한다. dp[] 배열구조: dp[시작0,1][남은 자릿수][남은 성냥개수] 왜 첫번째 배열을 ..

[Java] BaekJoon 1725. 히스토그램, BaekJoon 6549. 히스토그램에서 가장 큰 직사각형(모노톤스택)

히스토그램 문제출처: https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제이해 목표 주어진 히스토그램에 대해, 위그림처럼 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 풀이 정답 도출 매커니즘 이해 현재 인덱스(now) 기준으로 - 왼쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (left[now]) - 오른쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (right[now]) - righ..

[Java] BaekJoon 14226. 이모티콘 (BFS) (골드5)

문제출처: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제이해 목표 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. (2 DP와 BFS로 풀이 (탐색 우선 순위는 해당 이모티콘을 출력하기까지 Price(시간)가 낮은 순서대로) min[]: 최소 걸리는 시간을 다루는 배열 인덱스: i개의 이모티콘, 값: i개의 이모티콘을 만드는데 걸리는 시간의 최솟값 1. 증식 방법 - 자기보다 1 적은 이모티콘으로 탐색 -> min..

[Java] BaekJoon 3197. 백조의호수(BFS) (플레5)

문제출처: https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제이해 목표 2마리의 백조가 호수에서 살고 있다. 이 둘을 만나게 해주자 ! - map에는 빙판과 물이 존재한다. - 백조는 물 위로 밖에 다닐 수 없다. - 물을 끼고 있는 빙판은 하루가 지나면 녹아 물이 된다. 며칠이 지나여 백조들이 만날 수 있는지 계산해보자 ! 풀이 2개의 BFS 진행이 필요하다 !! [1] 백조1을 기준으로 BFS(백조2를 찾기위한..

[Java] BaekJoon 2696 중앙값 구하기 (골드2) (힙에 대한 이해)

문제출처: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 문제이해 목표 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 풀이 흐름 Queue 2개를 만든다. 비교적 작은 수들이 모여있는 leftQueue -> 내림차순 정렬 (큰 수 먼저 나오게) 비교적 큰 수들이 모여 있는 rightQueue -> 오름차순 정렬 (작은 수 먼저 나오게) 핵심은 홀 ..

[Java] BaekJoon 2579. 계단오르기 (DP) (실버3)

문제출처: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제이해 목표 각 계단에는 점수가 있고, 계단을 오른다. - 최대 점수 획득이 목표 조건 - 연속된 세 개의 계단을 밟아서는 안된다. - 계단은 한계단을 오르거나 뛰어 넘을 수 있다. - 마지막 도착 계단은 반드시 밟아야한다. 풀이 1. 조건이 연속된 세 개의 계단이므로 (처음의 첫 3계단은 예외처리 하거나 데이터 읽어놓기) 2. arr[ i ] => i번째의 계단 점수 DP[ i ] => i번째까..

[Java] BaekJoon 1890. 점프 (DP)(백트래킹) (실버2)

문제출처: https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제이해 목표 게임판에서, 정해진 숫자를 밟은 만큼 오른쪽이나 아래쪽으로 점프 (0,0) -> (N,N)으로 갈 수 있는 경로 수를 찾는 문제 *주의: 0을 밟으면 이동할 수 없다. 풀이 -> dfs 탐색 도착 노드에 도달하면 해당 경로로 백트래킹해서 갈 수 있는 경로의 가짓수 DP를 갱신함 주의 0 밟은 경우를 고려 안하면 무한히 탐색을 진행하여 StackOverFlow 오..

[Java] Programmers 위클리챌린지12주차_피로도(Level 2) (순열)

문제출처: https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 12주차 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 문제이해 목표 유저의 현재피로도: k 각 던전별 정보: dungeons[i][] - 2번째배열의 첫번째값[0]: 최소 피로도 - 2번째배열의 두번째값[1]: 소용 피로도 위 정보를 가지고 유저가 탐험할수 있는 최대 던전 수를 구하시오 풀이 첫번째 풀이. 순열로, 던전을 도는 순서의 모든 case를 찾아서(탐색후), 돌 수 있는 던전만 coun..