![]()
문제 출저 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 풀이 5X5 격자에 이다솜파 S 와 임도연파 Y 가 주어집니다. 7개의 인접한 칸을 선택합니다. 이 때 이다솜파 S가 임도연파 Y보다 커야 합니다. (즉 임도연파가 4이상이 되면 안됩니다.) 이 때, 이 조건을 만족하는 경우의 수를 구하는게 문제의 요구사항 입니다. 백트래킹으로 풀었습니다. 25개의 칸 중 7개를 선택했습니다. (7C25 라 시간초과가 발생하지 않습니다.) 이 때, 칸..
![]()
문제 출저 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 풀이 계랸아 n개 주어진다. 각각의 계란은 내구도와 무게를 가지고 있다. 계란끼리 부딫이면 서로의 무게 만큼 내구도가 감소한다. 내구도가 0 이하가 되면 깨진 것으로 한다. 왼쪽부터 계란을 들어 깨지지 않는 계란과 부딫힌다. 이 때 깨진 계란은 들지 않는다. 계란끼리 부딫혔을 때, 계란이 최대한 많이 깨진 갯수를 구하는게 이 문제의 요구사항이다. 백트래킹으로 풀었습니..
![]()
문제 출저 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 높이 h, 넓이 w 인 격자판이 주어집니다. 격자판 안에는 레이저를 이어야 하는 지점인 C 2개와 벽인 *, 레이저가 지나가는 . 으로 이루어져 있습니다. 이 때 거울을 설치하면 레이저의 방향을 90도 바꿀 수 있습니다. C끼리 레이저로 연결하기 위해 최소한의 거울 갯수를 구하는 것이 문제의 요구사항 입니다. 다익스트라 알고리즘으로 풀었습니다. int[h][w][4]..
![]()
문제 출저 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 풀이 가수의 순서가 들어오고 이 순서들을 모두 만족하는 순서를 구해야 합니다. 또한 모두 만족할 수 없을 경우 0을 출력해야 합니다. 위상 정렬로 풀었습니다. 가수들의 순서를 입력받을 때 가수의 간선 정보와 앞에 몇 명의 가수가 와야하는지를 저장했습니다. 만족하지 못 했을 경우는 사이클을 구하는 방식으로 구했습니다. 사이클의 형성은 총 갯수 N이 아닌 경우 입니..
![]()
문제 출저 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 풀이 장난감의 종류와 각 장난감이 조립되기 위한 부품들을 알려줍니다. 이 때, 부품은 기본 부품과 중간 부품이 있습니다. 기본 부품은 다른 부품 조립에 사용되는 부품으로 다른 부품으로 조립할 수 없는 기본 부품 입니다. 중간 부품은 부품들로 이루어진 부품들입니다. 최종 완제품 N을 조립하는게 기본 부품이 몇 개 필요한지 구하는게 이 문제의 요구사항 입니다..
![]()
문제 출저 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 풀이 수식이 주어졌을 때 괄호를 적절히 추가하여 최댓값을 구하는게 이 문제의 요구사항 입니다. 저는 DFS로 풀었습니다. List number를 선언해 수식에 숫자를 순서대로 담았습니다. List operation을 선언해 수식에 연산 기호를 순서대로 담았습니다. dfs(int stage, int left)를 선언합니다. stage는 operation 의 순서이고 ..
![]()
문제 출저 https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ www.acmicpc.net 문제 풀이 총 N개의 케릭터의 level이 주어집니. k는 레벨을 올릴 수 있는 총량입니다. 이 때 k를 적절히 분배해여 최소값을 가장 높게 만드는게 이 문제의 요구사항 입니다. 저는 이분 탐색으로 문제를 풀었습니다. 최소 레벨을 탐색에 대상으로 하였습니다. 최소값은 주어진 레벨의 최소값으로 하였고 최댓값은..
![]()
문제 출저 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 문제 풀이 회전 초밥의 가짓수와 순서가 주어집니다. 이 때 연속한 k개의 초밥 + 이벤트 초밥을 더했을 때 최대한 다양하게 먹은 초밥의 가짓수를 구하는 것이 이 문제의 요구사항입니다. int[] board = new int[n+k] 를 선언합니다. 일차원 정수 배열 board는 초밥의 순서는 담는다. 이 때, 회전 초밥이므로 끝은 처음과 이어..
![]()
문제 출저 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 풀이 n일 동안 하루에 써야할 금액과 인출할 횟수 m이 주어집니다. 인출은 현재 가지고 있는 돈이 하루동안 써야할 금액보다 작을 때 이루어 집니다. 인출을 할 때, 기존에 가지고 있는 돈은 모두 통장에 넣습니다. (즉 초기화 된다는 얘기) 이 때, 한 번에 인출 횟수 m번을 만족하는 최저 금액을 구하는게 문제의 요구 사항 입니다. (제 기준, 문제가 모호하게 적혀있어 이해하는데 시간이 ..
![]()
문제 출저 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 주어진 예산을 최대로 쓰는 상한액을 구하는게 이 문제의 요구사항입니다. 상한액을 구하기 위해 이분 탐색을 활용했습니다. int[] board에 주어진 값을 담았습니다. 이분 탐색을 위해 상한액의 범위를 int s, int e로 선언했습니다. int s 는 가장 작은 값으로 0을 했습니다. 상한액의 최대 한도(e)는 주어진 예산 값 중 가장 큰 값으로 했습니다 while(s
![]()
문제 출저 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 배열이 주어지고 배열의 다른 숫자로 배열의 숫자를 만들면 좋다 라고 합니다. 주어진 배열이 몇 개의 좋다가 있는지 구하는게 이 문제의 요구사항 입니다. 투 포인터로 문제를 풀었습니다. 다른 숫자이므로 투 포인트가 같으면 넘기는 조건을 추가했습니다. 소스 코드 package baekjoon.backjoon9.day15; import java.io.BufferedReader; import java.io.IO..
![]()
문제 출저 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열 2처럼 이분 탐색으로 대처해가면서 문제를 풀었다. 다만 이번에는 숫자의 범위가 음수여서 처음에 넣은 기본값을 0 이 아니라 Integer.MIN_VALUE 로 넣었습니다. 소스 코드 package baekjoon.backjoon9.day14; /* 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.n..
