본문 바로가기
  • 개발하는 곰돌이

구현10

[Kotlin] 백준 30036 : INK 문제 링크 30036번: INK 첫 번째 줄에 정수 $I$, $N$, $K$가 공백으로 구분되어 주어진다. $(1 \le I, N, K \le 100)$ 두 번째 줄에는 잉크 문자열이 주어진다. 세 번째 줄부터 $N$개의 줄에 걸쳐 $N \times N$ 크기의 스테이지가 주어진 www.acmicpc.net 문제 해설 특별한 알고리즘이 필요하지 않은 단순 구현 문제. 우선 스테이지를 입력받으면서 하얀 사각형의 현재 위치를 저장하고 충전된 잉크의 양과 현재 색상의 순서를 저장할 변수를 선언한다. 이때 하얀 사각형의 현재 위치인 @는 이후 구현을 편하게 하기 위해 .으로 치환해준다. 이후 문제의 조건을 차례대로 구현해보자. UDLR : 스테이지를 벗어나지 않는 범위 내에서, 스테이지의 목적지 값이 .인 경우.. 2023. 10. 25.
[Kotlin] 백준 6568 : 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 문제 링크 6568번: 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 그래서 여러분도 크리스마스날 심심해서 컴퓨터를 하나 만들었다. 이 컴퓨터는 아주 적은 수의 명령어를 사용하는 하나의 프로세서, 32바이트 메모리, 8비트짜리 가산기, 5비트짜리 프로그램 카 www.acmicpc.net 문제 해설 특별한 알고리즘이 필요하진 않은 아닌 단순 구현 문제. 뭔가 복잡해보이지만 차근차근 문제에서 요구하는 내용을 구현해보자. 먼저 컴퓨터의 메모리가 32바이트라고 되어있다. 또한 이 컴퓨터는 메모리와 프로그램 구문(명령어)를 공유한다는 조건이 있고, 각 명령어의 길이가 1바이트라는 언급이 있으므로 길이가 32인 정수 배열로 나타낼 수 있다. 각 명령어는 3비트의 명령어 종류와 5비트의 피연산자를 표현한다.. 2023. 8. 31.
[Kotlin] 백준 9519 : 졸려 문제 링크 9519번: 졸려 첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다. www.acmicpc.net 문제 해설 눈을 \(x\)번 깜박인 결과로부터 원래 단어를 찾아내야 한다. 처음에는 단순히 문제에서 주어진 연산을 \(x\)번 역수행해서 구해보려고 했는데 입력의 최대치가 10억인 것을 보고 시간 초과가 날게 뻔해서 다른 방법을 찾아보기로 했다. 예제로 주어진 테스트 케이스를 직접 돌려보면 일종의 규칙이 있다는 것을 볼 수 있다. 0은 최초 입력으로 주어진 단어이고, 각 회차는 이전 단어에서 문제에서 주어진 연산을 역수행한 결과이다. 첫번째 예제의 경우.. 2023. 4. 17.
[Kotlin] 백준 11637 : 인기 투표 문제 링크 11637번: 인기 투표 각 테스트 케이스는 첫 번째 줄부터 순서대로 출력된다. 최다 득표자가 과반수 득표를 했을경우에는 "majority winner R", 절반 이하의 득표를 하였을 경우엔 "minority winner R"가 되며, 최다 득표자가 없 www.acmicpc.net 문제 해설 간단한 구현 문제이다. 각 테스트 케이스마다 매 입력으로 주어지는 득표 수 중 최대치와 득표 수의 합계를 구한다. 최대 득표 수의 개수가 1이 아니면(= 최다 득표자가 2명 이상이면) "no winner"를 출력한다. 최대 득표 수의 개수가 1이라면 득표 수의 합계를 2로 나눈 값과 최대 득표 수를 비교하여 "majority winner R" 또는 "minority winner R"를 출력한다. Code.. 2023. 2. 8.
[Kotlin] 백준 18917 : 수열과 쿼리 38 문제 링크 18917번: 수열과 쿼리 38 3번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1, 4]이다. 6번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1, 4, 1]이다. 10번째 쿼리가 끝난 이후 배열의 상태는 [0, 3, 1]이다. www.acmicpc.net 문제 해설 수열, 배열이라는 말이 있어서 실제로 리스트를 만들어서 구현하려고 할 수 있는데 함정이 있다. 쿼리의 개수가 최대 50만개이기 떄문에 실제 리스트에 25만개의 요소를 추가하고, 합이나 XOR 결과를 25만번 출력하게 되면 \(250,001\times250,000=62,500,250,000\)가 되어 약 625초의 시간이 걸리게 된다. 따라서, 실제 리스트를 구현하지 않고 답을 구해야 한다. 문제에서 요구하는 출력은 모든 .. 2023. 1. 3.
[Kotlin] 백준 11387 : 님 무기가 좀 나쁘시네여 문제 링크 11387번: 님 무기가 좀 나쁘시네여 각 줄마다 "공격력", "힘", "치명타 확률", "치명타 피해비율", "공격속도 증가"의 수치를 나타내는 다섯 개의 정수가 공백을 사이에 두고 순서대로 주어진다. 첫 번째 줄은 무기를 장착한 크리의 www.acmicpc.net 문제 해설 문제 자체는 단순한 구현 문제지만 주의할 점이 있다. 전투력을 계산할 때 실수 계산을 많이 하게 되는데 컴퓨터는 내부적으로 모든 수를 2진법으로 저장하기 때문에 소수점 이하 부분은 정확하게 저장할 수 없고 근사치를 저장하게 된다. 이 과정에서 여러번의 연산을 하다보니 오차가 발생하여 식은 맞지만 답은 틀리는 경우가 발생할 수 있다. 따라서 BigDecimal을 사용하여 오차 없이 계산해야 한다. 이점만 주의하면 크리와 .. 2022. 12. 15.
[Kotlin] 백준 15595 : 정답 비율 계산하기 문제 링크 15595번: 정답 비율 계산하기 첫째 줄에 어떤 문제의 총 제출 횟수 N(1 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 제출의 정보가 제출 번호 순서대로 주어진다. 제출 정보는 총 7가지가 공백 하나로 구분되어져 있 www.acmicpc.net 문제 해설 BOJ의 정답 비율을 계산하는 알고리즘을 직접 구현해보는 문제다. 입력에 많은 정보가 있지만 문제의 조건을 봤을 때 필요한 것은 문제를 맞은 사람의 수, 문제를 맞은 사람이 이전까지 틀린 횟수, 문제를 맞은 사람의 유저 아이디만 있으면 된다. 우선 문제를 맞은 사람이 이전까지 틀린 횟수를 계산하기 위해 HashMap을 사용했다. 문제를 아무리 많이 틀려도 해당 유저 아이디가 최종적으로 문제를 맞추지 못한다면 분모에 .. 2022. 12. 10.
[Kotlin] 백준 11866 : 요세푸스 문제 0 문제 링크 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 해설 문제의 예시를 그림으로 나타내면 다음과 같다. 그림을 보면 다음에 나갈 사람의 위치는 시작 위치 + \(k\) - 1인 것을 알 수 있다. 즉, 다음 순서로 나갈 사람의 위치는 이전에 나간 사람의 위치에 \(k-1\)을 더하면 된다. 이제 남은 사람의 수가 \(k\)보다 작아졌을 때의 처리만 하면 되는데, 이 때는 앞에서 구해진 다음 순서로 나갈 사람의 위치가 남은 사람의 수보다 작아질 때까지 남은 사람의 수를 빼주면 된다. 나간 사람의 번호는 별도의 배열에 저장하고 문제의 조건에 맞는 형태로 출력하면 된다. Code fun .. 2022. 12. 8.

티스토리툴바