DFS5 [백준] 15684번 사다리 조작 (Java) 백준 15684번 사다리 조작 : https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 개인적으로 많이 어려웠던 문제다. 처음에는 bfs로 시도해봤지만 배열을 복사하는 탓에 메모리, 시간 초과가 떠서 dfs로 풀게 되었다. 평소에 사용하던 dfs의 방식으로 풀이하여 통과하긴 했지만, 모든 경우의 수를 전부 확인하며 최소값을 찾는 방법이기 때문에 시간이 오래 걸렸다. 따라서 이 문제에서는 dfs를 약간 독특하게 변형하여 풀었다. 사다리의 수를 0, .. 2020. 2. 27. [백준] 14501번 퇴사 (Java) 백준 14501번 퇴사 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 보자마자 DP 문제라고 느낌이 왔지만, dfs로 더 쉽게 풀 수 있을 듯 해서 dfs로 풀게 되었다. 삼성 SW 역량테스트 기출 문제라고 해서 풀어봤는데, 생각보다 너무 쉬워서 깜짝 놀랬다. 총 걸린 시간 : 20분 난이도 : ★☆☆☆☆ 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int n, answer = .. 2020. 2. 25. [SW Expert] [모의 SW 역량테스트] 2115번 벌꿀 채취 (Java) SW Expert [모의 SW 역량테스트] 2115번 벌꿀 채취 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu 입력으로 각 벌통에 있는 꿀의 양이 주어졌을 때, 벌꿀을 채취하여 최대한 많은 수익을 얻어야 하는 문제이다. 입력으로 주어진 n의 값이 크지 않기 때문에 for문으로 모든 경우의 수를 전부 체크해주었다. 우선 벌통의 가장 앞의 index를 기준으로 노란색 벌통과 주황색을 선택해준다. solution 함수에서 4중 for문을 사용해서 두 벌통의 위치를 선택해주었다. 벌통의 위치가 고정이 되면, 이제 각 벌통에서 어느 값을 더해줄지를 판단한다. check 함수에서 각 벌통에서.. 2020. 2. 24. [SW Expert] [모의 SW 역량테스트] 1952번 수영장 (Java) SW Expert [모의 SW 역량테스트] 1952번 수영장 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 나는 이 문제를 dfs로 풀었지만, 풀이 후 다른 사람의 코드를 보니 DP로 푼 경우가 많았다. DP로는 각 단계마다 비용의 최솟값을 구하는 방식으로 푸는 듯 하다. 입력을 받을 때 1일치로 결제를 하는 것과 한 달을 결제하는 것 중에 작은 값을 배열에 저장한다. 그 뒤 dfs로 각각의 달에 어떤 방식으로 결제를 할지 선택한다. 결제 방식을 선택했다면 이용권 가격을 곱해서 총 비용을 계산해주면 된다. 총 걸린 시간 : 30분 난이도 : ★★☆☆☆ 코드 import java.i.. 2020. 2. 24. [SW Expert] [SW Test 샘플문제] 1767번 프로세서 연결하기 (Java) SW Expert [SW Test 샘플문제] 1767번 프로세서 연결하기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 상시 SW 역량테스트를 신청하기 전에 샘플문제로 풀어볼 수 있는 '프로세서 연결하기'이다. 최대한 많은 코어를 연결했을 때, 전선의 길이를 최소로 하는 값을 구하면 된다. bfs로 할지, dfs로 할지 고민을 하다가 bfs로 하면 배열 복사에 시간과 메모리 소모가 너무 많을 듯 하여 dfs로 풀이하게 되었다. 입력을 받을 때 코어의 위치들을 ArrayList에 저장한다. 그 뒤 코어의 위치에서 상하좌우로 연결이 가능한지 체크를 한다. (isConnect 함수) 연.. 2020. 2. 23. 이전 1 다음
