본문 바로가기

💯 | 백준70

[Kotlin, S3] 백준 1002번 터렛 터렛(1002번)Silver 3#수학 #기하학 #많은 조건 분기https://www.acmicpc.net/problem/1002 문제 내용 문제 접근입력 형식을 보면 터렛의 좌표와 마린과의 거리가 나온다. 이를 이용해 원을 이용하는 문제임을 유추할 수 있다.입력 예제 1의 첫 번째 case를 확인해 보자.0 0 13 40 0 37첫 번째 터렛의 좌표가 0, 0이고 마린과의 거리가 13이므로 반지름이 13인 원이라고 생각하면 된다. 첫 번째 터렛을 기준으로 다음과 같이 원을 구성하면 원의 둘레에 해당하는 부분들이 모두 마린이 있을 수 있는 경우의 수인 것이다.두 번째 터렛도 구성해 보자. 두 번째 터렛은 좌표가 40, 0이고 마린과의 거리는 37이다. 두 번째 원은 다음과 같이 구성된다. 그럼 첫 번째 .. 2024. 8. 20.

[Kotlin, S3] 백준 1004번 어린 왕자 어린 왕자(1004번)Silver 3#수학 #기하학 문제 내용 문제 접근시작 좌표와 끝 좌표가 주어지고, 행성계의 중심 좌표와 행성계의 반지름이 주어질 때, 시작 좌표에서 끝 좌표로 이동하면서 진입 또는 이탈하는 행성계의 개수를 구해야 한다.행성계는 반지름과 중심 좌표가 주어진다. 시작 좌표와 행성계의 중심좌표 간의 거리와 끝 좌표와 행성계의 중심 좌표 간의 거리를 이용해 해당 행성계를 무조건 지나야 하는지 아니면 안 지나가도 상관없는지 알 수 있다. 시작 좌표와 행성계의 중심 좌표 간의 거리를 distanceStart, 끝 좌표와 행성계의 중심 좌표 간의 거리를 distanceEnd라고 할 때행성계와 시작, 끝 좌표 간의 관계가 3가지가 나올 것이다. distanceStart와 distanceEnd.. 2024. 8. 19.

[Kotlin, S3] 백준 2346번 풍선 터뜨리기 풍선 터뜨리기(2346번)Silver 3#자료 구조 #덱https://www.acmicpc.net/problem/2346 문제 내용 문제 접근입력 순서대로 풍선 안에 들어있는 종이에 적혀 있는 숫자가 입력으로 주어지고, 종이에 입력된 수만큼 이동해서 다른 풍선을 터뜨려야 한다. 종이의 숫자가 양수면 다음 번호 방향으로 움직이고, 음수면 이전 방향으로 움직인다. 터진 풍선에 쓰인 종이는 재사용하지 않는다.입력 예제 1을 예로 들어 보면53 2 1 -3 -11번째 풍선인 종이에 3이 적힌 풍선을 터뜨렸으면, 양수이기 때문에 4번째 풍선을 터뜨려야 한다. 4번째 풍선은 음수이기 때문에 왼쪽 방향으로 이동한다. 2까지 이동했으면 2번 이동한 것이다. 2 이전의 값인 3은 이미 터져서 사용했기 때문에 이 때는 .. 2024. 8. 19.

[Kotlin, S5] 백준 30010번 잘못된 버블정렬 잘못된 버블정렬(30010번)Silver 5#애드 혹 #해 구성하기https://www.acmicpc.net/problem/30010 문제 내용 문제 접근위 문제에 잘못된 방식으로 구현된 버블 정렬 함수가 있다.이 함수를 이용해 버블 정렬을 했을 때, 올바르게 정렬되지 않는 리스트를 출력하면 된다. 먼저 버블 정렬이 어떻게 이루어지는지 알아야 한다.버블 정렬은 현재 위치에서 자신의 앞의 값을 확인해서 자신보다 값이 작을 경우 서로의 값을 교환하는 방식으로 구현을 한다.물론 1번의 사이클로는 정렬이 바로 안 되는 경우가 많기 때문에 정렬할 List의 크기만큼 반복해 주면 정렬을 마칠 수 있다. size가 5인 List를 4번의 사이클을 돌아 정렬을 완료한 부분이다.현재 자신의 앞의 값을 확인하고 있기 때.. 2024. 8. 17.

[Kotlin, S5] 백준 1813번 논리학 교수 논리학 교수(1813번)Silver 5#애드 혹 문제 내용 문제 접근입력받는 숫자가 i이면 i개의 말은 참이다라는 뜻이다.i개의 말이 참이 되기 위해서는 i가 2라면 2개의 말이 참이 되어 있어야 한다. 그렇지 않으면 이 문장은 거짓이 된다.다르게 말하면 "정확하게 2개의 문장이 참이다." 라는 말은 입력받은 말들 중에서 2개만 참일 때만 참이 된다. 그러므로, 입력값(i)의 빈도 수가 같은 경우는 참이 되게 된다.하지만 고려해야 할 사항이 있다. 모순(-1)인 경우와 모순이 아니지만 참이 하나도 없어서 0인 경우이다.-1인 경우는 입력 예제 2의 경우이다.10위의 경우에는 "정확하게 0개의 문장이 참이다." 라고 말하는 문장이 1개가 있다고 말하기 때문에 모순적이다라고 하는 듯하다. 정답이 0인 경우.. 2024. 8. 16.

[Kotlin, B1] 백준 1952번 달팽이2 달팽이 2(1952번)Bronze 1#수학 #구현 #시뮬레이션https://www.acmicpc.net/problem/1952 문제 내용 문제 접근M * N의 2차원 리스트를 시계 방향으로 돌면서 꺾인 지점이 총 몇 개인지 구하는 문제이다.주의해야 하는 점은 한 번 지난 부분은 다시 지나지 못한다는 것이다.수학적으로 규칙을 찾아서 해결하는 방법이 있지만, 멍청한 관계로 무지성 전체 탐색을 할 것이다. 2차원 리스트를 boolean형으로 생성하면 한 번 지난 부분을 true로 설정하고 조건을 달면 돼서 한 번 지난 부분을 체크할 때 편하다. 문제 해결 코드더보기import java.io.BufferedReaderimport java.io.InputStreamReaderfun main() = with(B.. 2024. 8. 14.

[Kotlin, S3] 백준 15649번 N과 M(1) N과 M(1)(15649번)Silver 3#백트래킹 문제 내용 문제 접근백트래킹을 이용해 해결 가능하다.완전탐색으로도 해결할 수 있지만 백트래킹을 쓰는 게 공부에 도움이 될 것 같다. 1부터 n까지의 자연수 중 중복 없이 m개를 고르는 모든 경우를 출력한다.백트래킹의 개념부터 간단하게 이야기하겠다. 백트래킹은 일자로 쭉 내려가다가 정답이 아님이 확실시되면 이전으로 돌아와서 다시 다른 경로로 검색을 시작하는 방법이다.간단하게 사진으로 진행 과정을 봐보자. 처음에는 0 -> 1 -> 3으로 이동하면서 탐색한다. 3에 도달하면 더 깊게 들어갈 수 없기 때문에 부모 노드로 다시 이동해서 다른 경로로 재탐색하는 방식이다. 부모 노드로 돌아가는 방법은 자식까지 dfs로 특정 깊이까지 들어가고 나면 저장하면서 방문.. 2024. 8. 13.

[Kotlin, G5] 백준 16928번 뱀과 사다리 게임 뱀과 사다리 게임(16928번)Gold 5#그래프 이론 #그래프 탐색 #너비 우선 탐색https://www.acmicpc.net/problem/16928 문제 내용 문제 접근1부터 100번째 칸까지 존재하는 뱀과 사다리 게임판이 존재할 때, n개의 사다리와 m개의 뱀이 있다.사다리를 밟으면 위로 이동하고 뱀을 밟으면 아래로 내려간다.입력 예제 1을 예로 들면3 732 6242 6812 9895 1397 2593 3779 2775 1949 4767 17사다리가 3개, 뱀이 7개 있고 2번째 줄부터 순서대로 사다리, 뱀을 입력받는다.숫자 2개가 있는데, 사다리 32 62를 예로 들면 32를 밟게 되면 62로 이동하고, 4번째 줄인 뱀 95 13의 경우는 95를 밟으면 13으로 내려간다. 주사위를 적게 돌리.. 2024. 8. 12.

[Kotlin, S1] 백준 11403번 경로 찾기 경로 찾기(11403번)Silver 1#그래프 이론 #그래프 탐색 #최단 경로 #플로이드-워셜https://www.acmicpc.net/problem/11403 문제 내용 문제 접근그래프에서 정점의 개수 N이 주어진다.입력 리스트 크기는 N * N이고, 한 줄에 정점이 여러 개이거나 없을 수도 있다.i번째 줄에 정점이 있으면 i번째 줄의 j번째 데이터에 있을 건데, j번째 줄의 입력값으로 가서 정점이 존재하는지 확인하는 작업을 해야 한다.자세하게 설명하자면, 입력 예제 2를 예로 들겠다.70 0 0 1 0 0 0 // 30 0 0 0 0 0 1 // 60 0 0 0 0 0 0 //0 0 0 0 1 1 0 // 4, 51 0 0 0 0 0 0 // 00 0 0 0 0 0 1 // 60 0 1 0 0 0 .. 2024. 8. 11.

[Kotlin, S1] 백준 6064번 카잉 달력 카잉 달력(6064번)Silver 1#수학 #브루트포스 알고리즘 #정수론 #중국인의 나머지 정리https://www.acmicpc.net/problem/6064 문제 내용 문제 접근카잉 제국의 달력 형식은 x : y 형식으로 이루어져 있고 x, y를 정하기 위해 m, n을 사용한다.위 문제 설명을 해석해 보자면 x m = 12일 때 x가 12가 되면 1로 초기화된다는 뜻이다. 이는 x가 1부터 12까지 반복된다는 뜻이다. y도 마찬가지이다.이 사실을 알았으면 눈치가 빠른 분들은 규칙 파악에 성공했을 것이다. 그럼 바로 코드를 작성하러 가시면 된다. 예를 들어 m = 10이고, n = 12일 때 마지막 해는 60이다.m이 10이면 x는 1부터 12를 반복해서 돌게 되고 y도 1부터 10까지 돌게 된다.해.. 2024. 8. 11.

[Kotlin, S3] 백준 31883번 FA수의 진 FA수의 진(31883번)Silver 3#수학 #구현 #그리디 알고리즘 #시뮬레이션 문제 내용 문제 접근입력이 순서대로 주어진다.횡단보도를 건너는 시간, 육교를 건너는 시간, 횡단보도가 초록불인 시간, 횡단보도가 빨간불인 시간위 순서대로 입력이 주어지는데, 횡단보도와 육교 중 더 시간이 적게 걸리는 방법을 찾아서 이용해야 한다. 그래야 최솟값을 구할 수 있으니. 횡단보도의 빨간불인 시간과 초록불인 시간을 판단을 잘해야 한다.입력 예제 중 1가지의 예시를 불러와 보겠다.1 2 2 4초록불인 시간은 2분이고, 빨간불인 시간은 4초다.이 에시를 보면 2분이 경과했을 때 횡단보도를 건널 수 있게 생겼지만 건너면 안 된다.정확히 2분이 되는 순간 빨간불이 되기 때문에 기다려야 한다.표로 나타내 보면 다음과 같다.. 2024. 8. 9.

[Kotlin, S5] 백준 9196번 정수 직사각형 정수 직사각형(9196번)Silver 5#브루트포스 알고리즘 #정렬 #런타임 전의 전처리 문제 내용 문제 접근문제에서의 직사각형의 크기를 판별하는 방법은 2가지이다.1. 대각선이 더 긴 직사각형이 더 큰 직사각형이다.2. 대각선의 길이가 같으면 높이가 더 높은 것이 더 큰 직사각형이다.이 2가지 조건을 이용해 입력받는 직사각형보다 큰 직사각형 중 가장 작은 직사각형을 출력해야 한다. 문제 조건이 직사각형 값이 150을 넘지 않는다고 한다. 이러면 전체 탐색을 해도 상관없는 제한이다.그래서 높이와 너비가 1부터 150까지의 직사각형들을 모두 뽑아서 정렬시키면 된다.하지만 문제에 조건이 있다. 1. 너비(w)가 높이(h) 보다 커야 한다.2. 직사각형만을 뽑아야 한다.위 2가지의 조건을 코드로 구현해 보자.. 2024. 8. 9.

[Kotlin, S5] 백준 1340번 연도 진행바 연도 진행바(1340번)Silver 5#구현 #문자열 #파싱 문제 내용 문제 접근날짜가 분까지 입력되기 때문에 진행도의 단위를 하루(365)로 정해서 진행도를 구하면 안 된다.하루에서 더 쪼개서 분으로 정해서 진행도를 구해야 한다. 하루를 분으로 변환하면 1440분이다. 백분율을 구하는 공식은 쉽다.입력받은 날짜가 1월 1일에서부터 얼마나 지난 날짜인지 구한 다음에, hour를 60을 곱해 더해주고, 분을 더해주면 1년에서 분을 기준으로 얼마나 지났는지 알 수 있다.이를 구해 365 또는 366으로 나눠서 100을 곱하면 정답이 된다.365 말고 366을 쓰는 이유는 윤년을 의식하기 위해서이다. 윤년은 2월이 29일까지 있기 때문에 하루가 더 길다.1월 1일로부터 얼마나 시간이 지났는지 분으로 환산한 .. 2024. 8. 8.

[Kotlin, B1] 백준 16433번 주디와 당근농장 주디와 당근농장(16433번)Bronze 1#구현https://www.acmicpc.net/problem/16433 문제 내용 문제 접근정사각형으로 이루어진 밭의 넓이인 n과 당근이 심어져 있는 위치 r, c가 순서대로 주어진다.당근을 밭에 심어야 하는데 조건이 있다.당근이 심어져 있는 위치에 위, 아래, 오른쪽, 왼쪽에 다른 당근이 심어져 있으면 안 된다.예제 1을 예로 들면 다음과 같이 당근이 심어져야 한다.위 사진과 같이 기존에 심어져 있던 당근을 기준으로 지그재그로 당근을 심어야 한다.첫 당근의 위치에 맞게 다른 당근의 위치를 구하려면 조건이 필요하다. 우선 r부터 봐보자. 지그재그가 되려면, 현재 당근이 심어져 있는 위치와 심을 당근의 거리 차이가 짝수면 똑같은 x위치에 당근을 심어도 된다. .. 2024. 8. 7.

[Kotlin, B2] 백준 31215번 이상한 섞기 연산 이상한 섞기 연산(31215번)Bronze 2#애드 혹https://www.acmicpc.net/problem/31215 문제 내용 문제 접근1부터 n까지 시작하는 수열 B가 있다. n이 5면 1, 2, 3, 4, 5로 구성되는 수열이 된다.k까지의 수열이 있을 때, k의 약수에서 가장 큰 2의 제곱수가 l이다.예를 들어 k = 4일 때, 4의 약수는 1, 2, 4이고, 여기서 가장 큰 2의 제곱수인 l은 4이다(2의 2승). k가 3인 경우에는 3의 약수 1, 3에서 가장 큰 2의 제곱수는 2의 0승인 1이 된다.l을 구하고 나면 수열의 k번째 index와 l번째 index를 교환한다.아 과정이 문제에 언급된 이상한 섞기 연산이다. 이상한 섞기 연산을 통해 변경한 수열에서 1이 들어 있는 index를.. 2024. 8. 7.

[Kotlin, G5] 백준 1013번 Contact Contact(1013번)Gold 5#문자열 #정규 표현식https://www.acmicpc.net/problem/1013 문제 내용 문제 접근입력받은 숫자 코드가 (100+1+ | 01)+ 을 만족하는지 확인해야 한다.위의 예시에서 봤다시피, +기호는 특정 문자가 반복해서 나오는 것을 뜻한다.100+의 경우에는 100, 10000, 1000000... 와 같은 숫자들이 100+ 를 만족한다.(01)+의 경우에는 괄호 안의 숫자들이 반복돼서 나오는 것을 뜻한다.01, 0101, 010101... 와 같은 숫자들이 (01)+ 을 만족한다. 우리가 확인해야 할 패턴은 (100+1+ | 01)+은1. 10 다음에 0이 반복된다. 그리고 반복이 끝나면 1이 반복된다.2. 01로 끝난다.패턴 1 또는 2가 반복.. 2024. 8. 7.

[Kotlin, S1] 백준 5525번 IOIOI IOIOI(5525번)Silver 1#문자열 문제 내용 문제 접근첫 줄의 입력으로 O가 몇 개 들어 있는지 확인한다.예를 들어 O = 1이면 IOI, O = 3이면 IOIOIOI이 된다. 다음과 같은 문자열을 IOI 문자열이라고 부르겠다.IOI 문자열이 3번째 줄에 입력되어 있는 문자열에 몇 개가 포함되어 있는지 구해야 한다.IOI 문자열이 IOIOI이고, 문자열이 IIOIOIOIIOO일 때는, 1. IIOIOIOIIOO 2. IIOIOIOIIOO 로 총 2가지의 경우를 구할 수 있다. 겹치는 경우까지 생각해야 한다. IOI문자열은 처음에 I로 시작하고 쭉 계속 OI가 반복된다는 규칙이 있다.O = 1일 때 IOI,O = 3일 때 IOIOIOI 인 것처럼.이를 이용해 처음에 시작 문자가 I로 시작하고.. 2024. 8. 6.

[Kotlin, S1] 백준 1389번 케빈 베이컨의 6단계 법칙 케빈 베이컨의 6단계 법칙(1389번)Silver 1#그래프 이론 #그래프 탐색 #너비 우선 탐색 #최단 경로 #플로이드–워셜 문제 내용 문제 접근각 사용자가 어떤 사용자와 관계를 맺고 있는지 확인해서 그래프를 돌면서 몇 번째 단계에서 원하는 사용자에게 닿을 수 있는지 확인해야 한다.입력 예제 1을 이용해 그래프를 먼저 구성해 주겠다. 그래프의 구성은 다음과 같이 해줄 수 있다.import java.io.BufferedReaderimport java.io.InputStreamReaderimport java.util.*import kotlin.math.minprivate var graph = arrayOf>()private var visited = booleanArrayOf()private var res.. 2024. 8. 5.

[Kotlin, S2] 백준 30804번 과일 탕후루 과일 탕후루(30804번)Silver 2#구현 #브루트포스 알고리즘 #두 포인터 문제 내용 문제 접근탕후루에 꽂혀 있는 과일의 종류는 총 9종류이고 만들어야 하는 탕후루는 특정 과일 2개가 연속되어 있는 탕후루 중 가장 긴 경우를 확인하는 것이기 때문에 9C2의 경우를 모두 체크해서 가장 긴 길이가 정답이 될 것이다. 길이를 체크하기 위해서는 일단 9종류의 과일 중에서 중복을 포함하지 않고 선택해야 하기 때문에 2중 반복문으로 2가지의 경우를 선택할 수 있다.자세한 설명은 조합 알고리즘을 검색해 보면 자세한 설명이 나올 것이다.범위는 과일 1부터 9까지이기 때문에 1..9로 설정해 준다. 그다음 선택된 두 과일이 입력값에 있으면 길이 카운트를 세줘야 한다.입력값이 두 과일 중 하나인 경우를 고르는 조건.. 2024. 8. 5.

[Kotlin, S2] 백준 21736번 헌내기는 친구가 필요해 헌내기는 친구가 필요해(21736번)Silver 2#그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색 문제 내용 문제 접근캠퍼스의 구조를 2차원 리스트의 구조로 띄운 다음에 방문 여부와 벽(X)인지 확인해 위치를 이동해 가면서 만나는 사람이 있는지 확인해 주면 된다.문제의 예제 1을 예로 들어 보겠다.3 5OOOPOOIOOXOOOXP현재 도연이의 위치가 I이기 때문에 시작 좌표를 I값이 있는 곳으로 지정을 해주어야 한다.그리고 도연이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있기 때문에 각 방향으로 이동했을 때 그 위치로 이동할 수 있는지 확인해 주어야 한다.이동할 수 있는 위치인지 확인하는 조건은 2가지를 써야 한다.1. 한 번도 방문한 적 없는 위치인지?2. 해당 위치가 벽(X)이 .. 2024. 8. 4.

[Kotlin, S2] 백준 18111번 마인크래프트 마인크래프트(18111번)Silver 2#구현 #브루트포스 알고리즘 문제 내용 문제 접근문제에서 주어진 높이는 0부터 256까지이다.이 높이를 이용해 반복문을 돌려서 높이가 g 일 때 높이가 g인 평평한 바닥을 만들기 위해 얼마나 시간이 걸리는지 확인해야 한다.그전에 입력된 값에서 어떤 높이의 블록이 몇 개 들어 있는지 확인해야 한다.그 값은 Map으로 저장할 것이다. key를 높이, value를 개수로 정하겠다.val block = mutableMapOf()이제 위에서 언급했다시피 0 ~ 256까지 반복해서 돌아 준다.돌면서 기존의 입력값에서 높이가 g인 평지를 만들기 위해 블록을 얼마나 캐고 설치해야 하는지 계산해야 한다.블록을 캐는 작업은 2초가, 블록을 설치하는 데는 1초의 시간이 소요된다.현재.. 2024. 8. 3.

이전 1 2 3 4 다음

728x90

티스토리툴바