처누

https://www.acmicpc.net/problem/25631문제 : 실버 5마트료시카는 속이 비어있는 인형이다. 성빈이는 N개의 마트료시카를 가지고 있다. i번째 마트료시카의 크기는 a_i이고, 마트료시카 속은 모두 비어있다.성빈이는 남아 있는 마트료시카 중에서 i번째와 j번째(i != j) 마트료시카를 고른 뒤에 i번째 마트료시카를 j번째 마트료시카 속에 넣을 수 있다. 단, j번째 마트료시카의 속이 비어있어야 하고, i번째 마트료시카보다 j번째 마트료시카가 더 커야 한다. 합친 후에는 남아 있는 마트료시카의 개수가 한 개 줄어든다.성빈이는 마트료시카를 최대한 합쳐서 정리하려고 한다. 성빈이가 마트료시카를 잘 합친다면 남아 있는 마트료시카의 최소 개수는 얼마일까? 풀이 과정해당 문제는 보자마자 ..

https://www.acmicpc.net/problem/25947문제 : 실버 1 n개의 선물 가격이 주어졌을 때, b의 예산으로 최대로 많은 선물을 사려고 한다. 이때 최대 a개의 선물에 대해서는 반값 할인을 받을 수 있다고 했을 때 최대로 살 수 있는 선물의 수를 구하는 프로그램을 작성하시오. 단, 한 선물에는 최대 한 번만 반값 할인을 받을 수 있다. 입력입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000), 예산을 나타내는 양의 정수 b (1 ≤ b ≤ 10^9), 반값 할인을 받을 수 있는 최대 선물의 수를 나타내는 정수 a (0 ≤ a ≤ n)가 공백을 사이에 두고 차례로 주어진다. 다음 줄에 n개의 선물 가격이 공백을 사이에 두고 ..

https://www.acmicpc.net/problem/2716문제 : 실버 2깊은 아마존 정글에 거대한 나무들에서 갈색 원숭이들이 매우 좋아하는 무화과가 열리고, 이 나무에는 향나무노린재들이 서식하고 있다.나무 꼭대기에 도달하기 위해서 원숭이들은 매우 조심스럽게 나무에 올라가는 길을 찾아야한다. 거대한 나무는 부서지기 쉬운 덩굴들이 있는데 이 덩굴들은 시소의 원리와 비슷하다. 덩굴의 무게가 불균형 하면 그 덩굴은 끊어지며 그 원숭이들은 땅으로 떨어져버린다. 원숭이들은 서로 협력하여 덩굴의 균형을 유지한다면 그들은 모두 무화과가 열리고 향나무노린재들이 서식하는 나무 꼭대기에 도달할 수 있다는 것을 발견했다.덩굴은 두개의 덩굴로 나눠질 수 있는데 덩굴이 끊어지지 않기 위해서는 나눠진 두 덩굴은 같은 수의..

https://www.acmicpc.net/problem/20546문제 : 실버 5 풀이 과정해당 문제는 준현이와 성민이 두 명의 주식 수익 경우를 구해줘야한다. 준현이의 경우는 현재 주가를 살 수 있는 돈이 있다면 무조건 사는 방식이다.( (현재 가지고 있는 돈) / (현재 주가) ) > 0 이라면 stcokCount에 몫만큼 더해주면 된다. 성민이의 경우는 준현이보다 조금 더 까다롭다.오늘 주가가 전날의 주가보다 크거나 작은 경우에 따라서 전액 매수할지 매도할지 달라지기 때문에 연속해서 며칠동안 오르고 내렸는지 count를 체크해줘야한다. 며칠동안 올랐는지는 int upCount, 내렸는지는 int downCount로 계산했고,upCount == 3일 때, 그 날의 주가로 현재 가지고 있는 주식을 ..

https://www.acmicpc.net/problem/3254문제 : 실버 3 풀이 과정해당 문제는 게임판에 던진 김밥 4개가 먼저 연속적이게 만드는 사람을 출력하는 문제다. 처음에 문제를 잘못 해석하여 상근이와 정인이가 각자의 게임판에 김밥을 던지는 줄 알고 구현했더니 예제 입력3에서 오답이 나와 문제를 다시 해석했다. 하나의 게임판에 두 명이 김밥을 던지는 게임이고, 김밥을 게임판에 던지면 그 즉시 게임판의 맨 아래로 떨어진다고 생각하고 문제를 풀면 쉽게 풀 수 있다.김밥 4개가 연속으로 이어져 있는지 확인할 때는 int[] dx, int[] dy를 두고 이어져 있는지 확인하는 로직을 사용했다. 풀이 코드public class Ex3254 { private static int[] dx = {-..

https://www.acmicpc.net/problem/20207문제 : 골드 5 풀이과정해당 문제는 회의실 배정 문제와 비슷한 문제처럼 보인다. 처음 문제를 보고 든 생각은 우선순위 큐를 활용하는 것이었다. 하지만 우선순위 큐로 구현했을 때, 날짜가 겹치는 경우 해당 날짜를 다시 저장하여 사용해야하는데 마땅히 최적화 할 수 있는 방법이 생각나지 않았다. 예시로 나와있는 달력과 코팅지의 면적은 보면 높이는 겹친 날짜의 최대 갯수, 길이는 일정이 없는 날을 기준으로 가로 길이를 카운트해주면 되는 것을 볼 수 있다.여기서 생각난 방법은 int[] 배열을 두고 각 일정이 있는 날짜마다 1을 더해주는 것이다. 이 방법으로 구현한다면 입력 값을 정렬할 필요도 없이 카운트만 해주면 되기 때문에 최적화된 방법이라고..

https://www.acmicpc.net/problem/11507문제 : 실버 4 풀이과정해당 문제는 여러 자료구조를 이용하여 풀 수 있다고 생각한다. 나는 int[][] 이차원 배열에 P,K,H,T를 각각 인덱스 0,1,2,3으로 치환하여 이미 나온 숫자를 1로 체크하는 방법을 선택했다. 또한, 카드의 남은 갯수를 체크하기 위해 int[] cardCount를 선언하여 Arrays.fill(cardCount, 13)을 호출하여 카드 모양별 값을 13으로 초기화 시켰다. 이미 int[][]의 값이 1인 숫자가 또 나온다고 한다면 "GRESKA"를 출력하고, 아니라면 int[] cardCount 배열에서 1씩 감소시켜 남은 카드의 갯수도 체크해주면 된다. 정답 코드public class Ex11507 { ..

https://www.acmicpc.net/problem/25594문제 : 실버 5 풀이 과정해당 문제는 Map을 사용하면 쉽게 풀 수 있는 문제다. 다만 Map에 값을 저장하는 과정이 조금 귀찮을 뿐!!Map에 문제에서 주어진 HG 표준음성기호 표를 저장한 후에 입력 받은 값에 대해 replaceAll로 치환한다면 쉽게 풀 수 있다.다만, 여기서 주의해야 할 부분은 원래 단어로 출력해야하기 때문에 알파벳으로 변환해줘야 하는데 예제 입력1의 경우에 조심해야한다.//입력cauaespaunix//출력cau 이 경우 cau가 c로 또 replace가 될 수 있다. 문제에서 모든 입력은 소문자로 입력되고, HG 표준음성기호 표에도 모두 소문자이기 때문에 replaceAll() 할 때 알파벳 대문자로 먼저 치환 ..

https://www.acmicpc.net/problem/17471문제 : 골드 3 제한 2 ≤ N ≤ 101 ≤ 구역의 인구 수 ≤ 100 풀이과정해당 문제는 그래프와 BFS를 활용하여 푸는 문제다. 구역이 연결이 되어있는지 확인하는 조건만 신경쓴다면 어려움 없이 풀 수 있는 문제다. 그래프 문제는 항상 단방향인지 양방향인지 체크를 해주고 그래프 배열에 저장해줘야 한다. 두 개의 선거구를 나누는 과정에서는 조합을 이용하였다. n의 범위가 10까지이기 떄문에 시간복잡도도 충분하다.1번 선거구 : [1]2번 서거구 : [2, 3, 4, 5, 6]1번 선거구 : [2, 3, 4, 5, 6]2번 서거구 : [1] 위의 예시를 보듯 두 개의 선거구로 나뉘었지만 결국은 똑같은 선거구로 취급해도 된다. 따라서 조합..

https://www.acmicpc.net/problem/26162문제 : 실버 5 풀이 과정해당 문제는 문제의 입력 조건에 있는 a의 범위까지의 소수만 판별해낸다면 쉽게 풀 수 있는 문제다.해당 문제를 풀기 위해 저번 포스팅에서 사용했던 에라토스테네스의 체를 사용했다. 에라토스테네스의 체 알고리즘을 처음 듣거나 헷갈린다면 아래 문제를 먼저 풀고 오면 도움이 된다. [백준/Baekjoon] 1929번 : 소수 구하기 - 자바/Java [백준/Baekjoon] 1929번 : 소수 구하기 - 자바/Javahttps://www.acmicpc.net/problem/1929문제 : 실버 3 풀이과정문제는 소수를 구하면 되는 것이기 때문에 굉장히 쉬워 보인다. n이 1,000,000 이하의 자연수이기 때문에 공약수..