💻 Problem문제 보러 가기  N개의 돌이 일렬로 나열되어 있다. N개의 돌에는 왼쪽부터 차례대로 수 A1A2...Ai...AN로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.항상 오른쪽으로만 이동할 수 있다. i번째 돌에서 j(i돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자. 💡 Approach이중반복문을 통해 i번째 돌에서 j번째 돌로 이동할 때 드는 힘을 계산한다.힘이 K 이하이면 이동할 수 있다.이 정보를 바탕으로 인접 리스트를 만든다. 만든 인접 리스트를 이용해 dfs를 돌려 0번째 돌에서 N-1번째 돌까지 이동할 수 있는지 확인한다. ✏️ Solu..

💻 Problem문제 보러 가기 n과 xi가 주어진다. n은 10만 이하이고, xi는 절댓값이 100 이하인 정수이다. 💡 Approach문제의 식을 처음 봤을 때는 이중반복문이 생각났다.하지만 n의 최댓값이 10만(10^5)이므로 이중반복문으로 풀면 시간 초과가 된다. 만약 이중반복문으로 푼다고 생각하면i가 0일 때, x[0] * x[1] + x[0] * x[2] + ... 이고x[0] * (x[1] + x[2] + ...)i가 1일 때, x[1] * x[2] + x[1] * x[3] + ... 이고x[1] * (x[2] + x[3] + ...)...이런 식일 것이다. 이는 각 x[i]가 이후 원소들과 모두 곱해지는 구조이기 때문에 x[i]를 공통 인수로 묶을 수 있다.x의 모든 원소의 합을 구해놓..

💻 Problem문제 보러 가기 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.안전 거리가 가장 큰 칸을 구해보자. 💡 Approach상어의 위치를 기준으로 bfs를 퍼뜨려서 모든 칸의 안전 거리를 구하고 해당 배열의 칸들을 검사해서 안전 거리가 가장 큰 칸을 찾아 출력하도록 했다. 먼저 상어들의 위치를 찾아서 sharks 배열에 위치를 기억하고 보드의 상어 칸을 -1로 초기화한다.빈 칸은 모두..

💻 Problem문제 보러 가기 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.아래에는 세 가지 예가 있다....XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... ..XXX..

💻 Problem문제 보러 가기 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 💡 Approach백준이가 숫자를 하나씩 말할 때마다 지금까지 나온 수들 중에 중간값을 말해야 한다.지금까지 나온 숫자의 개수가 홀수면 가운데 값, 짝수면 ..

💻 Problem문제 보러 가기 오늘도 블롭은 배고프다. 그래서 블롭은 요리사 연우를 찾아가 맛있는 것을 달라고 부탁했다.연우는 귀여운 블롭에게 이왕이면 맛있는 음식을 해 주고 싶었기에, 자신이 만드는 데에 가장 뛰어난 애플파이를 만들기로 하였다. 연우는 N개의 애플파이를 만들었으며, 이를 원 모양으로 책상에 배치해 놓았다.각 애플파이는 하나의 양의 정수로 표현되며, 이는 맛있는 정도를 의미한다. (수가 클수록 더 맛있는 애플파이이다.)블롭은 N개의 애플파이 중 K개를 먹으려고 한다. 물론 블롭은 힘을 들이지 않고 먹고 싶기 때문에, 연속으로 배치되어 있는 K개의 애플파이를 먹으려 한다.블롭을 도와서 블롭이 먹을 애플파이의 맛의 합의 최댓값을 구해 주자! ✏️ Solution 1import sysinp..

💻 Problem문제 보러 가기 아주대학교는 1973년에 개교하여 올해로 개교 50주년을 맞이했다.이에 기뻐한 선우는 어떤 수에 50이 들어가면 그 수를 한 번 더 세기로 하였다.예를 들어 5152는 한 번만 세지만 5050이나 5051은 한 번 더 센다.선우의 방식대로 1부터 차례대로 수를 셀 경우, 몇 번째 수를 셀 때 N이 처음으로 등장하는지 구하여라. 선우의 방식대로라면 50은 50번째 수에서 처음 등장하지만, 51은 52번째 수에서 처음 등장한다. 💡 Approach브론즈 문제긴 한데 처음에 문제 이해가 안 됐음.. 1부터 숫자를 세다가 숫자 안에 "50"이 들어가 있으면 그 숫자를 한 번 더 세는 규칙1 → 1번째...49 → 49번째50 → 50번째 ← "50"이 들어가니 한 번 더 셈5..

💻 Problem문제 보러 가기 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주할 수 있는 구역의 지도를 만들어 지구로 보냈다.상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다.지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하는 프로그램을 작성하시오. 💡 Approach..