개발개발

1. 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2. 풀이 DP를 사용해서 풀이한다. 2X1, 1X2 타일을 이용해 채우므로, 3XN에서 N이 홀수일 경우 타일로 채워질 수 없다. 자바 배열에서는 배열 선언시 0으로 초기화 되므로 별도로 값을 초기화해주지 않아도 된다. 경우를 2가지로 나누어서 생각한다. 3X2를 채울 수 있는 경우는 3개이다. N-2개의 타일을 채운 경우 뒤에 2X1을 채워넣는다고 생각하면, DP[N] += DP[N-2] * 3이다. 4X2, 6X2, 8X2.... 4 이후 2의 배수마다 2가지 방법으로 칸을 채울 수 있는 방..

1. 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2. 풀이 BFS를 이용해 풀이한다. 별도로 방문 배열을 사용하지 않고 방문한 부분을 2로 값을 변경했다. 이 문제에서 중요한 것은 방향을 정하는 것이다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽 인데, 표에 해당하는 방향을 미리 배열로 지정해 놓고 왼쪽으로 이동할 때 (기존 방향 + 3) % 4로 다음 방향을 설정해준다. 청소를 ..

1. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 DP를 이용해 풀이한다. 2차원 배열로 DP를 진행한다. 첫번째 인덱스는 무게를 의미한다. dp[k][n]일 경우, k 무게 만큼 버티고 있을 때다. 두번째 인덱스는 물품의 인덱스를 의미한다. dp[k][n]일 경우, n번째 물건까지를 고려했을 때다. 즉, DP 배열에 저장되는 값은 인덱스에 해당하는 물건들의 ..

1. 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 카드 묶음의 합이 가장 작기 위해선, 가장 적은 카드 합(또는 카드)를 2개를 계속해서 합하는 것이다. 즉, 오름차순 정렬된 우선순위 큐를 사용해 가장 작은 카드 합을 2개 빼내고 이 두 카드의 합을 구한 후 구한 합을 다시 우선순위 큐에 넣으면 가장 적은 카드 합을 구할 수 있다. 3. 코드 import java.util.*; import java.io.*; ..

1. 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 2. 풀이 상어의 위치를 DFS를 이용해 움직인다. 상어와 물고기를 각각 객체를 만들어 사용한다. 물고기(Fish)는 좌표, 물고기 번호, 방향, 살아있는지 여부를 멤버 변수로 갖는다. 상어(Shark)는 좌표, 방향, 먹은 물고기 번호의 합을 멤버 변수로 갖는다. 물고기 번호를 입력 받고, 탐색을 시작하기전, 물고기를 번호 순서대로 먹기 위해 물고기가 담긴 list를..

1. 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 풀이 총 5개의 블록이 있는데, 이 중 ㅜ 블록(분홍색 블록)을 제외하고는 DFS 4번을 통해 대칭, 회전을 한 모든 블록의 모습을 구할 수 있다. 따라서, ㅜ를 제외한 4개의 블록은 DFS를 통해 4개 칸의 합을 구하고, ㅜ는 별도의 함수를 통해 4개 칸의 합을 구한다. 모든 칸에서 4개 블록타입을 모두 확인해야 하므로, 처음 DFS를 호출 할 때 백트래킹을 사용한다.(81~83..

1. 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 2. 풀이 가장 빠른 횟수를 구하기 위해 BFS를 사용한다. 구슬이 굴러가면 파란 구슬과 빨간 구슬이 같이 굴러가게 되므로, 두 구슬의 위치를 모두 담은 클래스를 선언해 사용한다. 맨 처음 구슬의 위치를 저장해 BFS를 시작한다. 구슬들의 위치 방문여부를 확인하기 위해 4차원 배열을 사용한다.(visited[n][m][n][m]) 4 방..

1. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. DFS를 이용해 한 사람씩 팀에 추가시키고 이를 boolean 배열에 저장한다(boolean[] visited) 선택한 사람의 수가 n/2인 경우, 즉 두 팀이 결성된 경우 두 팀의 점수차를 구한다. 두 팀의 점수차가 0인 경우 이미 최솟값이므로 프로그램을 종료한다. 3. 코드 import java.util.*; import java.io.*; class Main{ s..

1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 벽을 세울 위치를 선택할 때 DFS, 바이러스가 퍼지는 과정은 BFS를 이용해 풀이한다. 입력을 받을 때, 바이러스가 있는 좌표(값이 2인 부분)은 따로 저장해둔다. DFS를 이용해 벽을 세운다. 재귀함수를 이용해 DFS를 구현한다. map 중 벽을 세울 수 있는 부분(map[i][j] == 0)에 벽을 세운다.(map[i][j] = 1) 3개의 벽을 모두 세울때까지 재귀함수를 호출해 이..

1. 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 기호별 사용할 수 있는 남은 갯수를 담은 배열(markCnt)에서 0이 아닌 경우, 즉 기호를 사용할 수 있는 경우 기호를 사용한 계산을 한다. 모든 경우를 구하기 위해 재귀함수 실행 후, 기호별 사용할 수 있는 갯수를 다시 늘려준다.(markCnt[i]++) 계산식을 끝까지 구한 경우, 이전..