💻 Problem문제 보러 가기 세준이는 1부터 N까지 모든 수를 차례대로 공백 없이 한 줄에 다 썼다. 그러고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.) 💡 Approach1부터 숫자를 하나씩 늘리면서 입력값과 비교한다.그 숫자 역할이 n이고 입력값은 num이다.n을 하나씩 늘리면서 num의 한 글자씩 비교한다.n에 들어가는 숫자에 num[i]가 ..

💻 Problem문제 보러 가기 길이가 N인 수열 A_1, ..., A_N이 주어집니다. 수열의 모든 수는 서로 다른 1 이상 N 이하의 수입니다. 아래 조건을 모두 만족시키는 (i, j) 정수쌍의 개수를 구하세요. 1 . A의 i번째 수부터 j번째 수까지가 오름차순으로 배열되어 있다. 즉, i k에 대해 A_k . 💡 Approach처음에 예제 이해가 잘 안됐는데 문제 내용은 아래와 같다. (i, j) 구간의 수열이 정렬된 연속한 부분수열이면 만족한다.만족하는 경우의 (i, j) 정수쌍 개수를 구하면 된다. N의 범위가 1 반복문을 하나만 쓰는 방법을 생각해야 한다. 오름차순 구간 길이에 따른 (i, j) 쌍 개수를 구해보면 아래와 같다.오름차순 구간 길이(i, j) 쌍 개수가능한 (i, j) 쌍1..

💻 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의 모든 원소의 합을 구해놓..