문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 이 문제는 투 포인터 문제이다. 그냥 모든 경우의 수를 다 보면 O(N^2)으로 시간초과가 발생한다. 투 포인터 방식을 사용하면 O(N)에 문제를 해결할 수 있다. 나는 슬라이딩 윈도우 방식처럼 투 포인터를 사용하고 HashMap을 사용하여 해결하였다. 예를 들어 8 30 4 30 7 9 7 30 2 7 9 25 위와 같은 예제는. {7,9,7,3..
문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 이 문제는 간단한 DP 문제였다. maxDp와 minDP를 따로 나누어서 해결하면 간단하다. 우선, maxDp의 경우는 아래와 같은 점화식을 세우면 된다. maxDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최댓값 ( 0
문제 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 이 문제는 최장 증가 부분 수열(LIS) 문제이다. LIS에 대해서는 다음 게시글이 설명을 자세하게 있으니 참고하자 https://sskl660.tistory.com/89 [Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence) *최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 ..
문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 처음에는 단순 DFS로 문제를 접근했다. 하지만 DFS를 사용하면 시간 초과가 발생한다. 이 문제는 DP를 사용해서 해결해야 한다. 점화식을 아래와 같이 세우면 된다. dp[i][j] = i번째 집을 j 색깔로 칠할 때 비용의 최솟값 dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) // 이때 j와 같은 숫자는 제외..
문제 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 모든 숫자를 계산해서 저장하는 것은 메모리의 한계로 가능하지 않다(10000*10000=1억 개의 int) 따라서 숫자는 계속해서 계산해나가면서, 범위에 있는 배열에만 값을 저장하면 된다. 이때 map[r2-r1+1][c2-c1+1] 을 선언해서 사용하면 된다. 자세한 내용은 코드를 참고하자. 코드 HTML 삽입 미리보기할 수 없는 소스
문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 단순 구현 문제이다. 꼼꼼히 작성하는 게 중요하다! 나는 이 문제를 다음과 같이 해결했다. 먼저, 원판은 2차원 배열 circle [][]을 이용해서 표현했다. 이후 두 가지 함수를 작성했다. 1. 원판을 돌리는 함수 -> 시계, 반시계 방향을 기준으로 원판의 숫자를 돌린다. 인덱스 계산을 잘해야 한다. 2. 숫자를 지우는 함수 -> 모든 원소를 돌며 상하좌우를 탐색해 ..
문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 풀이 이 문제는 단순 구현 문제이지만, 풀기 쉽지 않았다. 내 풀이는 다음과 같다. [그림 1]과 같이 temp 배열을 만들고, 사각형의 테두리를 기준으로 왼쪽 위부터 반시계방향으로 원소를 탐색하면서 R칸씩 밀어서 (범위를 벗어나면 나머지 연산) 저장해놓는다. 이후 다시 똑같은 순서로 탐색하면서 t..
문제 https://www.acmicpc.net/problem/1669 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍 www.acmicpc.net 풀이 나는 수학 문제가 너무 어렵다. 이 문제는 수열 문제로 생각을 잘해야 풀 수 있다. 키차이 Day 1 Day 2 Day 3 Day 4 Day 5 1cm 1 2cm 1 1 3cm 1 1 1 4cm 1 2 1 5cm 1 2 1 1 6cm 1 2 2 1 7cm 1 2 2 1 1 8cm 1 2 2 2 1 9cm 1 2 3 2 1 키차이에 따른 키 크는 과정이다. 잘보면 4cm, 9cm 는 1,2,..
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 처음에는 모든 벽에서 BFS를 돌려 모든 벽마다 갈 수 있는 곳을 세려고 했으나 이렇게 하면 시간초과가 난다 ㅠㅠ 그래서 다른 방법을 생각해냈다. 모든 0의 묶음을 개수로 표시하고, 해당 벽에서 4방향을 조사해서 다른 묶음이라면 0의 개수를 더해주기만 하면 된다. 예를 들어, 아래와 같은 상황이 있다고 하자. 010 1x2 110 -> xx2 (x는 벽, 숫자는 0..
문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 꽤 까다로운 DFS+백트래킹 문제였다. 숫자가 행, 열, 3*3 보드에 존재하는지 O(1)에 체크하기 위해 1. HashSet row[10] 2. HashSet col[10] 3. HashSet board[10] 이렇게 3개의 HashSet 배열을 만들었다. 즉, 보드의 (x,y) 좌표에 특정 숫자를 넣으려고 하면, row[x] 와 col[y]에 해당 숫자가 있는지 체크하면 된다...