sw expert academy 2112번 보호 필름 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2112번 보호 필름 문제 정리 보호 필름은 얇은 막 D개를 쌓아서 만든다 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!) 각 셀들은 특성 A 또는 B를 가진다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경) 약품을 ..

sw expert academy 5656 구슬 깨기 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 5656 구슬 깨기 문제정리 구슬을 쏘아 벽돌을 깨드리려 한다. 벽돌이 있는 공간의 크기는 WxH이다. 구슬은 좌우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다. 벽돌은 숫자 1~9로 표현되며, 구슬이 명중한 벽돌은 상하좌우로(벽돌에 적힌 숫자-1)칸 만큼 같이 제거된다. 빈 공간이 있을 경우 벽돌은 밑으로 떨어지게 된다. N개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다. 벽돌을 떨어트린 후 남은 벽돌의 개수를 구하여라. 문제 풀이 모든 경우를 따져주기 위해서 중복 순열을 구해야 합니다. N이 3인 경우 000 ~ 999 (W=10)까지 모두 시뮬..

sw expert academy 2117번 홈 방법 서비스 자바(java) 풀이 모의 SW 역량 테스트 sw expert academy 2117번 홈 방범 서비스 문제정리 홈 방범 서비스는 마름모 모양으로만 제공된다. 서비스 영역의 크기 K가 커질 수록 운영비용이 커진다. 운영 비용 = K x K + (K - 1) x (K - 1) / K=2 일때 운영 비용은 2 x 2 + 1 * 1 = 5 이다. 이는 서비스 영역의 면적과 동일하다 도시를 벗어난 영역에 서비스를 제공해도 운영 비용은 변경되지 않는다. 홈 방범 서비스를 제공받는 집들은 각각 M의 비용을 지불 할 수 있다. 손해를 보지 않는 한에서 최대한 많은 집에 홈방법 서비스를 제공하려고 한다. 가장 많은 집들에 제공하는 서비스 영역을 찾고, 그 때의..

sw expert academy 1263번 사람 네트워크2 자바(java) 풀이 난이도 : D6 sw expert academy 1263번 사람 네트워크2 문제정리 Closeness Centrality(CC) : 네트워크 상에서 한 사용자가 다른 모든 사람에게 얼마나 가까운가? 사용자 i의 CC(i)는 다음과 같이 계산한다. 모든 dist(i,j)의 합 (단 dist(i,j)는 노드 i로부터 노드 j까지의 최단 거리) N은 1000 이하이다. 사람들의 CC 값중 최소값을 출력하여라. 문제 풀이 모든 노드에서의 최단 경로를 구하여야 합니다. 즉 All pairs shortest path problem이 됩니다 이는 플로이드-워셜 알고리즘을 이용하여 구할 수 있습니다. 1. 플로이드 워셜 알고리즘 한 정점에..

sw expert academy 1260번 화학물질2 문제 자바(java) 풀이 난이도 : D6 sw expert academy 1260번 화학물질2 문제정리 이 문제는 조건이 많으므로 잘 읽어보아야 합니다. 그리고 이 문제를 풀기전에 행렬찾기(1258번) 문제와 금속막대(1259번) 문제를 풀어보시는 것을 추천드립니다. 창고에 n*n 배열 형태로 화학 물질들이 있다. 빈 용기는 0 화학 물질이 들어 있는 용기는 화학 물질의 종류에 따라 1~9 사이의 값을 가짐 화학물질이 담긴 용기들이 사각형을 이루고 있다. 사각형 내부에는 빈 용기가 없다. 화학 물질이 담긴 용기들로 이루어진 사각형들은 각각 차원이 다르다. (열과 행의 개수가 서로 다르다) 2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 ..

sw expert academy 3282번 0/1 Knapsack 문제 자바(java) 풀이 난이도 : D3 sw expert academy 3282번 0/1 Knapsack 문제정리 1~N번 까지 번호를 부여 받은 N개의 물건과 최대 K 부피 만큼 물건을 넣을 수 있는 가방이 있다. 각 물건은 부피 Vi와 가치 Ci를 가지고 있다 (각 값은 최대 100) 물건들 중 몇개를 넣어서 가방에 들어간 물건들 가치의 합을 최대가 되게 하려고 한다. (이때 부피의 합이 K를 초과하면 안된다) 문제 풀이 점화식을 세워서 문제를 풀 수 있습니다. 즉 DP 테이블을 만들 것입니다. object의 첫번째 열[i][0]은 물건의 부피를 두번째 열[i][1]은 가치를 나타냅니다. 행 i는 i번째 물건을 넣는경우, 열 j는 ..