SY DevLog

3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 다른 풀이를 참조하여 문제를 풀었다. 세그먼트 트리로 푸는 방법이다. 우선, n+m 크기로 배열을 만들어야 한다. 0부터 (m-1) 인덱스까지는 0으로 초기화를 하고, m부터 (n+m-1) 인덱스까지는 1로 초기화를 한다. 0이 들어간 공간은 빈공간을 의미한다. DVD를 꺼내서 맨 위에 쌓을 때마다 이 빈공간의 맨아래(m-1)에서부터 1로 채워진다. 원래 DVD가 있던 위치의 1은 0으로 변경된다. n번 DVD가 위의 배열 중에 어디에 있는지 그 위치(인..

13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 그리디 문제이다. N일째부터 1일째까지 거꾸로 돌면서, n일째에 할 수 있는 과제들 중 가장 점수가 큰 과제를 처리한다. 먼저, 6일째 처리할 수 있는 과제는 5점짜리 과제 하나이다. 따라서 5점짜리 과제를 한다. sum = 5 그 다음 5일째 처리할 수 있는 과제는 하나도 없다. 이미 5점짜리 과제를 해결했기 때문이다. 4일째에 처리할 수 있는 과제는 10점짜리, 40점짜리, 60점짜리가 있다. 이 중에서 가장 큰 점수를 가지는 과제는 60점짜리 과제이다. 따라서 4일째에는 60점짜리 과제를 처리한다. s..

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) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..