💻 Problem문제 보러 가기 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. n은 양수이며 11보다 작다. 💡 Approach dp[1] = 1dp[2] = 2dp[3] = 4dp[4] = 7dp[5] = 13...직접 세보면서 점화식을 구한다.dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 예를 들어, dp[5]의 경우, 5를 1, 2, 3 조합으로 더해야 한다.1로 시작하는 조합, 2로 시작하는 조합, 3으로 시작하는 조합을 구해보면 아래..

💻 Problem문제 보러 가기 여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 A가 주어진다. A에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 다음, 식당 입구에 줄을 서서 대기하는 학생 수가 최대가 되었던 순간의 학생 수와 이때 식당 입구의 맨 뒤에 대기 중인 학생의 번호를 출력하자...

💻 Problem문제 보러 가기 창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다.'.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이 연결된 선분을, '\'은 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점이 연결된 선분을 나타낸다.창영이가 그린 도형의 넓이를 출력하는 프로그램을 작성하시오. 💡 Approach처음엔 어려울 거라고 생각했는데 풀고 나니 쉬운 문제였다. '/'나 '\'은 무조건 넓이가 0.5이다.'.'의 넓이는 1이지만, 문제는 안쪽 도형의 영역인지 바깥쪽 빈 영역인지를 알아야 한다. 도형이 완성된다는 조건이니 '/'나 '\'로 도형을 열었으면 안쪽 영역, 이를 다시 닫았으면 바깥쪽 영..

💻 Problem문제 보러 가기 "피터팬 프레임"은 단어를 다이아몬드 형태로 장식하는 것이다.알파벳 X를 피터팬 프레임으로 장식하면 다음과 같다...#...#.#.#.X.#.#.#...#.."웬디 프레임"은 피터팬 프레임과 유사하지만, 다이아몬드를 '*'로 만드는 것이다. 알파벳 X를 웬디 프레임으로 장식하면 다음과 같다...*...*.*.*.X.*.*.*...*..단어가 주어졌을 때, 3의 배수 위치(세 번째, 여섯 번째, 아홉 번째, ...)에 있는 알파벳은 웬디 프레임으로, 나머지 알파벳은 피터팬 프레임으로 장식하는 프로그램을 작성하시오.웬디 프레임과 피터팬 프레임이 겹칠 경우에는, 웬디 프레임이 위에 있다. 첫째 줄에 알파벳 대문자로 이루어진 최대 15글자 단어가 주어진다. 💡 Approa..

💻 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..