본문 바로가기

💯 | 백준59

[Kotlin, S5] 백준 11116번 교통량 교통량(11116번)Silver 5#구현 #브루트포스 알고리즘 문제 내용 문제 접근다리의 왼쪽에서 오는 차들(들어오는 차)의 시간과 오른쪽으로 나가는 차들의 시간이 주어졌을 때, 문제에 언급된 규칙을 이용해 다리를 지난 차들이 몇 대인지 구하면 된다. 왼쪽에서 오는 차의 시간이 t, t + 500이고, 오른쪽으로 나간 시간이 t + 1000, t + 1500이 있는 경우가 다리를 지난 차가 된다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val n = bf.readLine().toI.. 2024. 11. 15.

[Kotlin, S2] 백준 2232번 지뢰 지뢰(2232번)Silver 2#그리디 알고리즘 #정렬https://www.acmicpc.net/problem/2232 문제 내용 문제 접근지뢰를 모두 터트리는 최소 개수를 구해야 한다.직접 터트리는 지뢰의 개수를 최소로 하려면 연쇄적으로 터지는 지뢰의 개수가 많은 곳을 위주로 터트리면 된다. 직접 터트리는 지뢰의 위치에서 왼쪽 방향은 오름차순으로 수가 정렬되어 있어야 하고, 오른쪽 방향은 내림차순으로 정렬되어 있어야 한다.예를 들어 다음과 같이 지뢰가 있을 때,1 2 5 4 3 3 6 6 2 3, 7, 8번의 지뢰를 직접 터트리면 모든 지뢰를 제거할 수 있다. 지뢰가 연쇄적으로 터지려면 왼쪽은 오름차순으로 중복 없이 정렬되어 있어야 하고, 오른쪽은 내림차순으로 중복 없이 정렬되어 있어야 한다. 오름.. 2024. 10. 21.

[Kotlin, B1] 백준 31432번 소수가 아닌 수 3 소수가 아닌 수 3(31432번)Bronze 1#수학 #애드 혹 #정수론 문제 내용 문제 접근n개의 숫자를 사용해서 소수가 아닌 수가 있으면 yes를 출력하고 소수가 아닌 수 하나를 아무거나 출력하고, 소수가 아닌 수가 없을 때는 no를 출력하는 문제이다.각 숫자는 중복해서 사용할 수 있다. 약간의 수학적 고민이 필요한 문제이다. 같은 숫자를 중복해서 쓸 수 있다는 경우 때문에 no가 나오는 경우는 하나도 없다.n개의 숫자가 2, 3, 5, 7인 경우에는 n의 숫자들이 모두 소수이지만, 같은 숫자를 여러 번 쓸 수 있으면 22, 33, 55, 77처럼 소수가 아닌 수를 언제든지 만들 수 있다는 뜻이 되기 때문에 n에 어떤 수가 나와도 no가 나오는 경우가 없어지는 것이다. 그러면 정답을 같은 수를 사용.. 2024. 10. 17.

[Kotlin, P4] 백준 10000번 원 영역 원 영역(10000번)Platinum 4#자료 구조 #정렬 #기하학 #스택https://www.acmicpc.net/problem/10000 문제 내용 문제 접근우선 문제 이해부터 해보자.간단하다.원을 x축에 구성하고 난 후, 영역을 세면 된다. 영역의 개수는 다음과 같이 세면 된다. 원의 영역과 원끼리 접하면서 나뉜 영역도 생각해야 하고, 원 바깥의 영역도 처리해야 한다.원끼리 접하면서 나뉘게 되는 영역을 나누는 방법을 생각해야 하기 때문에 어렵다. 초기 구현 아이디어를 떠올리기 위해 아래의 블로그를 참고해서 구현했다.https://wonyoung2257.tistory.com/79 [백준 python] 10000번 원 영역[백준 python] 10000번 원 영역 레벨: 플레티넘5 언어: 파이썬 htt.. 2024. 10. 14.

[Kotlin, G5] 백준 1711번 직각삼각형 직각삼각형(1711번)Gold 5#브루트포스 알고리즘 #기하학 #피타고라스 정리 문제 내용 문제 접근각 주어지는 점에서 무작위로 중복되지 않게 3개를 골라 만들 수 있는 직각삼각형의 개수를 구해야 한다.점의 개수가 1500개까지 있고, 시간제한이 5초이다.결정적으로 브루트포스 알고리즘으로 분류되어 있다.이는 최대 1500개의 점에서 3개를 골라야 할 때, 무지성 탐색이 가능하다는 뜻이다. 무지성 탐색에서 나온 3개의 점에서 각 점 사이의 길이를 구하고 그 길이를 피타고라스 정리 공식을 이용해 직각삼각형인지 파악하면 된다.두 점 (x1, y1), (x2, y2)가 있을 때, 두 점사이의 거리는(x2 - x1) * (x2 - x1)의 제곱 + (y2 - y1) * (y2 - y1)의 제곱에 루트를 씌운 값.. 2024. 10. 1.

[Kotlin, G4] 백준 9935번 문자열 폭발 문자열 폭발(9935번)Gold 4#자료 구조 #문자열 #스택https://www.acmicpc.net/problem/9935 문제 내용 문제 접근첫 번째 줄의 문자열에서 두 번째 문자열이 존재하지 않을 때까지 문자열을 제거한 결과를 출력하는 문제.문자열이 제거되고 남은 문자열들은 서로 붙어서 새 문자열이 된다. 단순히 문자열을 확인해 보면서 문자열을 제거해 나가면 되는 간단한 문제이다.그래서 일단은 replace를 반복시켜서 진행해 보았다.while (true) { val replaceRes = string.replace(removeStr, "") if (replaceRes != string) string = replaceRes else break}결과는 메모리 초과, 애초에 repl.. 2024. 10. 1.

[Kotlin, S2] 백준 14430번 자원 캐기 자원 캐기(14430번)Silver 2#다이나믹 프로그래밍https://www.acmicpc.net/problem/14430 문제 내용 문제 접근wook이 0, 0에서 n, m까지 이동할 때, 오른쪽, 아래쪽으로만 이동하면서 자원을 캘 수 있을 때, n, m까지 도달했을 때, 얻을 수 있는 자원의 최대 개수를 구해야 한다. 얻을 수 있는 최대 자원 개수를 구하는 방법은 입력 예제 1을 예로 설명해 주겠다.5 40 1 0 00 0 1 01 1 0 01 0 1 01 1 0 0// init dp array0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0 처음의 0, 0 부분은 입력값을 그대로 사용한다.그러면 2차원 array를 모두 0으로 초기화했을 때 0, 0에는 0 또는 1이 오게 될 것이.. 2024. 9. 30.

[Kotlin, S4] 백준 2358번 평행선 평행선(2358번)Silver 4#자료 구조 #정렬 #해시를 사용한 집합과 맵https://www.acmicpc.net/problem/2358 문제 내용 문제 접근2개 이상의 점을 지나는 선분에서 x축 또는 y축에 평행한 선분의 개수를 세는 문제.선분의 구성이 2개 이상의 점을 지날 수도 있고, 한 좌표에 점이 여러 개가 있을 수도 있다.// 선분의 구성에 2개 이상의 점이 쓰이는 경우41 02 03 04 0정답: 1// 한 좌표에 여러 점이 있는 경우21 11 1정답: 2첫 번째 case가 이해하기 어려웠다.문제를 처음 읽었을 때는 2개 이상의 점을 지나는 선분이라는 것을 못 보고 2개의 점을 지나는 선분이라고 생각해서 왜 1개가 나오는지 헷갈렸다.case 1의 경우에는 점 4개를 연결한 y축과 평행.. 2024. 9. 26.

[Kotlin, S5] 백준 32344번 유물 발굴 유물 발굴(32344번)Silver 5#구현 #기하학https://www.acmicpc.net/problem/32344 문제 내용 문제 접근운동장에 a번 유물이 w, h 위치에 묻혀 있다.a번 유물 조각들의 위치 정보를 이용해 a번 유물의 예상 크기를 직사각형으로 정의한다.직사각형의 넓이가 가장 큰 유물의 번호와 그 넓이를 출력한다.만약 넓이가 동일하다면 유물 번호가 더 작은 게 더 우선이다. 유물의 예상 크기 직사각형을 구하는 방법은 아래와 같다.예를 들어 4개의 위치에 유물이 있을 때점 a, b, c, d가 유물의 위치라고 하면 유물의 예상 크기는 사각형 efgh와 같다.위 사진으로 가장 큰 x축(d)과 가장 작은 x축(a), 그리고 가장 큰 y축(c)과 가장 작은 y축(b)의 값을 이용해 위 도형.. 2024. 9. 23.

[Kotlin, B1] 백준 32343번 드랍 더 비트 드랍 더 비트(32343번)Bronze 1#그리디 알고리즘 #브루트포스 알고리즘 #비트마스킹2024 HICON 홍익대학교 프로그래밍 경진대회 B번https://www.acmicpc.net/problem/32343 문제 내용 문제 접근n자리의 2진수에서 각각 1의 개수가 a, b개인 2진수 2개가 주어질 때, 두 2진수의 xor 연산 결과가 제일 큰 경우를 구해야 한다.n자리의 2진수에서 나올 수 있는 수는 2의 n승에 - 1만큼 나온다.예를 들어 3자리의 2진수에서 나올 수 있는 최댓값은 2의 3승에 -1이므로 7이다. 1부터 7까지 나올 수 있다는 뜻이다. 그래서 1부터 n자리의 2진수에서 나올 수 있는 최댓값만큼 반복해서 반복되는 수를 2진수로 변환 후, 1의 개수를 확인해서 1의 개수가 a, b개.. 2024. 9. 23.

[Kotlin, S4] 백준 9242번 폭탄 해체 폭탄 해체(9242번)Silver 4#구현 #문자열 #파싱https://www.acmicpc.net/problem/9242 문제 내용 문제 접근별 기호(*)와 공백으로 이루어진 숫자가 입력된다.숫자는 7 segment 숫자 표기법으로 이루어져 있다.그냥 숫자를 파싱 해서 6으로 나누어 떨어지면 beer를 출력하고 그렇지 않으면 boom을 출력하면 되는 간단한 문제이다. 또한 암호가 무조건 7 segment의 숫자들만 나오는 것도 아니다.암호는 3 * 5의 형태로 1칸씩 공백을 띄고 주어지게 되는데, 3 * 5의 암호 형식을 지키지 않은 코드가 올 수 도 있다.그래서 위 2가지 상황에 맞는 처리(boom)를 해주어야 한다. 문제 해결 코드더보기import java.io.BufferedReaderimpor.. 2024. 9. 20.

[Kotlin, B1] 백준 21771번 가희야 거기서 자는 거 아니야 가희야 거기서 자는 거 아니야(21771번)Bronze 1#구현 #문자열https://www.acmicpc.net/problem/21771 문제 내용 문제 접근가희(G)와 베개(P)가 입력될 때, 가희가 베개 위에 있으면 1, 아니면 0을 출력베개 위에 있는 조건이 G가 P에 걸쳐 있어도 베개 위에 있다고 친다. 1이 출력되려면 P의 영역 안에 G가 있어야 한다.그것을 확인하기 위해서는 P의 개수를 세면 쉽게 알아낼 수 있다.P의 개수가 P 영역의 넓이보다 작으면 G가 P 영역 안에 있다는 것을 뜻한다.입력 예제 1을 예로 들어 보자.11 115 4 6 10....GGGG.......GGGG.......GGGG....PPPGGGGPPP.PPPGGGGPPP.PPPPPPPPPP.PPPPPPPPPP.PPPP.. 2024. 9. 19.

[Kotlin, G5] 백준 10827번 a^b a^b(10827번)Gold 5#임의 정밀도 / 큰 수 연산https://www.acmicpc.net/problem/10827 문제 내용 문제 접근a에 소수가 들어오고, b에 지수가 들어올 때, a의 b제곱을 구하기.소수(a)의 b제곱이라, 소수를 정확히 계산할 BigDecimal을 사용한다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.math.BigDecimalfun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val input = readLine().split(" ") val a = BigDecimal(input.. 2024. 9. 19.

[Kotlin, B1] 백준 25551번 멋쟁이 포닉스 멋쟁이 포닉스(25551번)Bronze 1#수학https://www.acmicpc.net/problem/25551 문제 내용 문제 접근포닉스가 옷을 입는 규칙에서 눈여겨볼 것은 옷의 색이다.마스크와 티셔츠의 색이 달라야 하고, 티셔츠와 바지 역시 색이 달라야 한다.그러면 옷을 입는 경우의 수가 2가지로 좁혀진다.검은색 마스크 + 흰색 티셔츠 + 검은색 바지흰색 마스크 + 검은색 티셔츠 + 흰색 바지위 2개의 경우만 문제의 1, 2번 규칙을 만족하는 복장이다.이 복장에서 같은 색의 옷을 연속해서 입지 않기 때문에 1, 2번을 번갈아가면서 입게 된다.또한 1번 사용한 옷은 다시 입지 않기 때문에 옷이 모자라게 되면 연속해서 옷을 고를 수가 없다. 문제의 4번째 규칙으로 구현의 힌트를 얻을 수 있다.한 종류.. 2024. 9. 13.

[Kotlin, S2] 백준 18352번 특정 거리의 도시 찾기 특정 거리의 도시 찾기(18352번)Silver 2#그래프 이론 #그래프 탐색 #너비 우선 탐색 #최단 경로 #데이크스트라https://www.acmicpc.net/problem/18352 문제 내용 문제 접근도시의 개수, 도로의 개수, 구해야 하는 최단 거리와 시작 지점이 주어질 때, 시작 지점 도시에서 다른 도시로 이동하는 최단 거리가 입력받은 최단 거리와 같은 도시 번호만 출력한다. 조건에 맞는 도시가 없으면 -1을 출력. 도시는 모두 1~N까지가 있다. 도로의 길이는 모두 1일 때, 최단 경로 입력값을 K라고 할 때, 출발 도시에서 각 도시로 이동하는 최단 경로가 K와 같은 도시만 출력한다.bfs를 사용하면 된다. bfs를 쓰기 위해서는 어쨌든 그래프가 있어야 한다.4 4 2 11 21 32 3.. 2024. 9. 10.

이전 1 2 3 4 다음

728x90

티스토리툴바