📚 문제 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 🔍 아이디어 처음에는 그냥 기본적인 bruteforce풀이를 진행하였다. 골드 문제에 어울리지 않는다고 생각했는데 바로 시간초과가 났다. 이 풀이를 그대로 멀티버스 1번에 넣으니 통과되었다(브론즈 5) 못풀겠다 하고 침대에 누워있었는데 각 행성에 등수를 매기고 그 등수가 동일한 우주가 있다면 동일하게 균등하다고 할 수 있을 것 같다는 생각이 들었다. 그래서 싹 정렬을 하고 등수를 매겼다. 등수를 매길때 동일한 숫자는 동일한 등수를 주어야 하기 때문..
📚 문제 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 🔍 아이디어 최대한 적은 강의실을 사용하여 모든 수업을 할 수 있도록 하는 문제입니다. 처음 문제를 읽었을때는 그리디 문제로 생각하고 끝시간을 기준으로 정렬하고 모든 경우를 확인하였으나 그렇게 하면 시간 초과가 발생합니다. 다른 문제 풀이방법은 강의를 입력받는 경우 시작시간, 끝 시간을 구분하여 입력받고 시작시간인 경우에는 필요한 강의실이 하나 증가, 끝 시간인 경우는 필요한 강의실이 하나 감소하도록 하여 한 시점에 최대 몇개의 강의실이 ..
📚 문제 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 🔍 아이디어 사각형을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 묶은 후에 해당 영역이 모두 같은 색으로 칠해져있다면 숫자를 입력하고 칠해져 있지 않다면 다시 한분 4등분 분할하여 한영역이 모두 같은 색이 될때까지 진행하며 영역의 값을 구해나간다. 예제 입력 8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011 예제 출력 ((110(0101))(0010)1..
📚 문제 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 🔍 아이디어 종이의 반을 접는 경우 A | B 와 같다면 A와 B는 접는기준으로 대칭적이라는 특징이 있다. 해당 특징을 이용하여 중간점을 기준으로 A와 B가 대칭인지 확인하고 A와 B종이도 종이의 절반을 기준으로 대칭적인지 계속해서 재귀적으로 탐색한다. 예제 입력 3 0 000 1000110 예제 출력 YES NO YES 📝 풀이 import java.io.BufferedReader; import java.io.IOException; import j..
📚 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🔍 아이디어 1. 재귀적 풀이는 숫자 3개를 고르는 과정이 조합과 같기 때문에 해당 방식을 이용하였습니다. 2. 반복문 풀이는 숫자 3개를 고르는 과정을 3중 포문을 이용해서 arr에서 i, j, k숫자를 뽑는 경우에 대해서 목푯값과 비교하여 문제를 해결할 수 있습니다. 📝 풀이 1. 재귀적 import java.io.BufferedReader; impor..
✨ HINT 숫자를 아예 4,7로 구성해 보는 방식 숫자를 4,7로 구성한 후에 a와 b사이에 속하는지 확인하는 방식 📚 문제 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔍 아이디어 범위가 1~1,000,000,000이기 때문에 모든 수에 대해서 4,7로 이루어져 있는지 판단하는 것이 시간이 너무 오래 걸릴 것이라 생각하였습니다. 다른 방법은 아예 숫자 자체를 4,7로 이루어지게 한 후에 min, max사이에 해당 값이 있는지를 판단하는 것이 낫다고 생각하여 해당 방식을 이용하였습니다. Int형의 범위..
처음 백준 알고리즘을 풀면서 귀찮게 하는 요인들 중 제출 시의 지정형식, 어디까지 돌아갔는지 모르는 것들의 요인이 있습니다. 기본적인 설정 1. 자신이 주로 사용하는 풀이 언어 설정을 설정합니다. 설정-> 언어그룹에서 자신의 언어를 드래그 앤 드롭을 사용하여 위로 올려주면 됩니다. 추가로 공개/비공개 여부는 언어그룹 및 소스코드 공개 배너에서 설정하면 됩니다. 사용하지 않는 언어는 언어 배너에서 같은 방식으로 드래그 앤 드롭하여 변경하면 됩니다. 2. solved.ac : 유저들의 랭킹과 자신의 랭킹을 볼 수 있습니다, 추가로 문제의 난이도를 표시해 줍니다. 상단의 유저이름 오른쪽 설정으로 들어가서 solved.ac를 활성화합니다.(저는 사용 중이기에 해당 선택이 없습니댜..) 또한 보기 탭에서 문제의 ..
📚 문제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🔍 아이디어 그리디 알고리즘으로 해결하였습니다. 해당 문제는 과제의 마감일과 과제의 점수를 주고 최대 얻을 수 있는 과제 점수를 찾는 문제입니다. 저의 경우는 보통의 그리디와 같은 문제인줄 알고 먼저 배열을 마감일을 기준으로 오름 차순 정렬하였습니다. 그 이후에 마감일을 돌면서 해당 마감일 안에 해결할 수 있는 과제들이 있는 경우 우선순위 큐에 넣고 큐에 값이 있는 경우 해당 날자에 해결 할 수 있는 문제가 있는 것임으로 점수가 가장 큰 것을 리턴하도록 하였습니다. 하지만 예제 출력 값과 달라 문제..
📚 문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🔍 아이디어 https://mathbang.net/101#gsc.tab=0 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정신 바짝 차리고 따라오세요. 원과 직선의 위치관계, 원의 할선과 접선, 접점에서 했던 것처럼 두 원이 어떤 관 mathbang.net 내접과 외접에 관한 문제입니다. 각 점을 기준으로 r 떨어진 거리에 사람이 있는경우는 원을 그려서 해당 해당 호 안에 사람이 있어야 한다는 소리로 인식했습니다. 따라서 두 원의 내접과, 외접..
📚 문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 🔍 아이디어 단순한 위상정렬 문제입니다. 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 과거에 다른 블로그에 작성한 글입니다. 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬..
