PS(Problem Solving)/BOJ244

• 

  [백준/BOJ] 2212번: 센서 문제 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 해설 문제를 요약해 보자면, n개의 센서와 k개의 집중국이 있을 때 집중국의 수신 가능영역의 최소 거리 합을 구하는 것이다. 센서는 평면상의 직선에 있으므로, 각 센서의 거리를 구하기 위해 오름차순으로 센서의 위치를 정렬해 준다. 문제의 예시 1을 보면 센서의 위치는 [1, 3, 6, 6, 7, 9]가 된다. 각 센서의 거리 사이는 [2, 3, 0, 1, 2]이 되는.. PS(Problem Solving)/BOJ 2023. 8. 22.

• 

  [백준/BOJ] 3197번: 백조의 호수 문제 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 해설 예전에 시도했던 문제인데 시간초과가 나서 포기했던 문제이다. 오늘 와서 다시 도전해 봤는데 역시나 어떻게 해야 시간초과를 해결할 수 있을지 감이 잡히지 않아 결국 구글링을 하여 이해를 하였다. 처음에 나는 백조를 움직이고, 물을 녹이고 즉, 2개의 큐만을 사용해 문제를 해결하려 했었다. 이 방법으로는 백조가 계속 모든 맵을 탐험하게 되므로 시간초과가 나게 된.. PS(Problem Solving)/BOJ 2023. 2. 13.

• 

  [백준/BOJ] 1149번: RGB거리 문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 해설 다른 알고리즘에 비해 DP에 취약한 것 같아 쉬운 문제부터 풀어보자라는 마음으로 풀어보았다. 이 문제는 어떻게 풀어야할까 고민하던 중 문제의 조건을 다시 한번 읽어보니 힌트를 찾을 수 있었다. 문제에는 3개의 조건이 있지만 결론적으로는 n번째 집은 n-1번째 집과 n+1번째 집과의 색이 달라야 한다는 것이다. 예를 들어 현재 위치의 집을 빨간색으로 하고 싶다면 이전.. PS(Problem Solving)/BOJ 2023. 2. 8.

• 

  [백준/BOJ] 1213번: 팰린드롬 만들기 문제 https://www.acmicpc.net/problem/1213 PS(Problem Solving)/BOJ 2023. 1. 17.

• 

  [백준/BOJ] 2503번: 숫자 야구 문제 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 해설 문제에 주어진 조건을 보자. 1에서 9까지의 "서로 다른 숫자 세 개"로 구성된 세 자리 수 즉, 0도 포함되지 않는다는 것이다. 따라서 123부터 987까지의 숫자 중 답이 될 수 있는 경우가 있다는 것이 된다. 단순하게 123부터 987까지를 반복문을 통해 모두 확인하며, 입력한 수에 대해 모두 만족한다면 답이 될 수 있는 경우가 된다. 즉, strike의 개수와 ball의 개수가 .. PS(Problem Solving)/BOJ 2023. 1. 16.

• 

  [백준/BOJ] 1937번: 욕심쟁이 판다 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 처음에 문제를 봤을 때 "아 가장 길이가 짧은 곳에서부터 시작하면 되겠구나" 라는 생각을 하였다. 하지만 예시를 보고서는 "어라? 이게 왜 이 값이 나오지?" 하고 보니 꼭 최소 길이부터 시작한다고 가장 많이 간다는 것이 아니었다. 쨌든 이 문제를 dfs를 통해 푼다는 것은 변하지 않는다. 여기에 더해 dp를 추가로 이용했는데, 모든 칸을 dfs로 돌리면 시간이 오래 걸려 시.. PS(Problem Solving)/BOJ 2023. 1. 11.

• 

  [백준/BOJ] 9466번: 텀 프로젝트 문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 해설 우선 배열의 인덱스는 0부터 시작이므로 각 학생을 0번부터 시작하도록 -1을 해준다. 예시 입력1의 첫번째 테스트 케이스는 다음과 같이 된다. 학생들은 서로 원하는 경우에만 팀이 될 수 있다. 즉, 사이클이 형성되야만 팀이 될 수 있다는 것이다. 우선 필요한 변수들을 생각해보자. 이미 방문했던 칸은 재방문할 필요가 없으므로 방문 여부를 처리해줄 visited 배열을 선언한다. 또한 사이클이 .. PS(Problem Solving)/BOJ 2023. 1. 10.

• 

  [백준/BOJ] 10451번: 순열 사이클 문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 해설 위 그림은 예제 입력의 첫 번째 테스트케이스이다. 색을 맞춰보면 case1. case2. case3 1 → 3 2 → 2 4 → 8 3 → 7 8 → 6 7 → 5 6 → 4 5 → 1 이처럼 3가지의 순환 사이클로 나뉘는 것을 확인할 수 있다. 이를 구현하는 방법을 알아보자. 나의 경우 Map에 인덱스와 값을 저.. PS(Problem Solving)/BOJ 2023. 1. 9.

• 

  [백준/BOJ] 14503번: 로봇 청소기 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 해설 처음 문제를 해결하려 할 때 방향에 대해서 헷갈렸지만 별거 없는 것이었다. "바라보고 있는 방향의 왼쪽에 청소하지 않은 칸이 있다면 그 칸으로 이동한다". 즉, 내가 북쪽을 보고 있을 때, 서쪽을 보고 청소가 되있지 않다면 청소하러 가라인 것이다. 다음으로 4칸이 모두 벽과 청소한 구역으로 이루어져 있어 이동할 수 없는 경우 방향을 유지한 채로 뒤로 한칸 간다. 이때 뒤의 방향이 벽이.. PS(Problem Solving)/BOJ 2023. 1. 4.

• 

  [백준/BOJ] 17086번: 아기 상어2 문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 해설 처음에는 0인 모든 지점에서 bfs를 수행시켜 가장 가까운 상어까지의 거리를 구하려고 하였다. 하지만 왠지 모르게 계속해서 답이 아닌 값이 나와 다른 방법으로 접근을 해보자는 생각을 했다. 여기서 생각해낸 것은 각 상어가 있는 지점부터 다른 상어가 있는 지점까지를 구해보자였다. 즉, 모든 상어가 있는 지점을 큐에 넣어준 후 bfs를 수행시키는 것이다. 과정은.. PS(Problem Solving)/BOJ 2023. 1. 3.

• 

  [백준/BOJ] 1644번: 소수의 연속합 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 해설 하나의 정수를 입력받고 이를 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다. 즉, 입력받은 정수까지의 소수 목록을 구하는 것이 첫번째 과정이 된다. 이때 에라토스테네스의 채를 이용하여 소수 목록을 구할 수 있다. private val primeList = mutableListOf(0) private fun eratosthenes(n: Int) { val arr = BooleanArray(n + 1) { true } for(i in 2 .. sqrt(n.toDouble()).toInt()) { .. PS(Problem Solving)/BOJ 2022. 12. 17.

• 

  [백준/BOJ] 14890번: 경사로 문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 해설 문제를 이해하는건 어렵지 않았지만, 코드를 짜고보니 깔끔한 코드가 아닌 것 같은 생각이 들었다. 한 클래스에 한 개의 책임만 지게 하고 싶었지만, 어떻게 나눠야 효율적일지 좀 더 생각을 해봐야겠다. 문제를 풀기 위해 생각해낸 순서는 다음과 같다. 각 높이를 입력받을 board 배열, 경사로를 놓았는지 검사할 check 배열을 선언한다. 가로로 길을 통과할 수 있는지, 세로로 길을 통과할 수 있는지 확인한다. .. PS(Problem Solving)/BOJ 2022. 11. 9.