SY DevLog

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net int[][] resttime = new int[N+1][N+1] : 각 칸마다 냄새가 없어지기까지 남은 시간 int[][] smell = new int[N+1][N+1] : 각 칸에의 냄새를 뿌린 상어의 번호(냄새가 없으면 0) int[][][] priority = new int[M+1][5][4] : 상어마다 현재 방향에서의 우선순위 ex) priority[m][1][0] : m번 상어의 현재 방향이 위쪽방향(1)일..

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 + 이진탐색으로 해결하였다. 처음에는 이진탐색으로만 문제를 풀었는데 시간초과가 났다. 세그먼트 트리에서 노드의 범위는 1부터 1000000까지이다. 사탕의 번호가 1부터 1000000까지 존재하기 때문이다. 각 노드에는 해당 사탕의 개수가 들어있다. A = 2인 경우, 사탕상자의 사탕에 변화가 생기므로 세그먼트 트리의 update() 메서드를 실행한다. A = 1인 경우, 수정이가 요구한 순위의 사탕이 어떤 맛의 사탕인지를 ..

1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제의 예제로 각 연주마다 가능한 볼륨을 표현하면 다음과 같다. 연주가 반복될 때마다 위의 그래프처럼 가지가 증가하므로 뒤로 갈수록 계산해야 하는 양이 많아진다. N의 범위가 최대 100이므로, N번째에는 2의 100승에 가까운 경우의 수를 검사해야 한다. -> 메모리 초과 혹은 시간 초과 다른 방법을 생각하다가 M+1크기의 배열을 생성하고, 다음과 같이 의미를 부여했다. int[] arr = new int[M+1]; arr..

20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 초록색 블럭과 파란색 블럭을 각각 boolean형의 2차원 배열로 생성한다. (i, j)칸에 블럭이 있으면 true, 블럭이 없으면 false가 들어간다. boolean[][] blue = new boolean[4][6]; boolean[][] green = new boolean[6][4]; 이 문제에서 크게 3가지 동작으로 나누었다. 1. 새로운 블럭 쌓기 : stack(int t, int x, int y) 2. 한 행(혹은 열)에 블럭이 다 차면, ..

1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 풀었다. 좌우대칭인 한 결과는 동일한 것으로 간주해야 한다는 점에서 처음에 점화식을 세우기 어려웠다. 만약 좌우대칭을 신경쓰지 않는다면 점화식을 다음과 같이 세울 수 있다. dp[n] = dp[n-1] + dp[n-2] * 2 타일의 가로 길이가 n일 때의 가능한 경우의 수는 ① 타일의 가로 길이가 n-1일 때에서 2x1짜리 타일을 하나 추가한 경우 -> dp[n-1] ② 타일의 기로 길이가 n-2일 때에서 2x2짜리 ..

17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 몇번째 원판인지, 해당 원판에 어떤 숫자가 있는지를 2차원 배열을 만들어서 저장한다. int[][] circle = new int[N+1][M+1]; x, d, k를 저장하는 Command 클래스를 만들고, T번마다 x, d, k 값이 다르므로 크기가 T인 배열을 생성한다. Command[] cmd = new Command[T]; 먼저, T번 반복하기 위한 반복문이 필요하다. 매번 cmd 배열에서 변수 x, d, k를 꺼내고, d가 0일 때(시계방..

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 다른 삼성역량테스트 문제에 비해 쉬운 편이었으나, 문제를 잘못 이해해서 몇시간을 삽질했다. 이동하려는 위치가 파란색이면, 방향을 바꾸고 반대편으로 이동해야 한다. 이 때, 반대편이 파란색이라면 이동하지 않는다. 여기까지는 제대로 이해했는데, 만약 반대편이 흰색이나 빨간색이면 A번 말 혼자만 이동하는 것이 아니라 A번 위에 있던 말들까지 같이 이동해야 한다. 하지만 문제에는 이 부분에 대해서는 설명이 생략되어 있어서 나는 계속 A번 말 혼자서만 이동시켰다. 이 ..

1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 동적 계획법을 통한 최장 공통 수열을 구하는 문제이다. 보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다. 아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다. lotuslee.tistory.com/39?category=964787 LCS(Longest Common Subsequence) LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 2740번 : 행렬 곱셈을 응용한 문제이다. B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다. 만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다. 이 때 B/2번 행렬을 곱한 ..

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍으로 해결할 수 있다. dp[n][l][r] : n번째 빌딩을 세울 때, 왼쪽에서 보이는 빌딩의 수가 l개, 오른쪽에서 보이는 빌딩의 수가 r개가 되도록 건물을 배치하는 모든 경우의 수 먼저, 처음으로 빌딩을 하나 세웠다고 치자. 건물이 하나밖에 없으므로 왼쪽에서 보이는 건물의 수는 1개, 오른쪽에서 보이는 건물의 수도 1개가 된다. -> dp[1][1][1] = 1 그 다음으로 두번째 빌딩을 하나 세운다. 그러면 두 가지 중 하나이다. 왼쪽에..