https://softeer.ai/practice/6287 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai풀이처음에는 BFS를 통해 가장 빠른 조립시간을 구하려 했다. 하지만 BFS로 수행할 시 메모리 초과가 발생했다.풀이방법에 대해 더 생각해보았더니 DP를 사용하여 해당 작업장까지의 최소 조립시간을 구하는 방식으로 풀었다.// 0 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하..

https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  풀이최장 증가 부분 수열 문제다.DP를 사용하여 풀 수 있으며 O(n^2) 의 시간복잡도를 가진다.DP를 사용하기 위해 돌의 개수 n만큼의 크기를 가지는 int형 1차원 배열 dp를 선언한다.dp[i] = i번째 돌이 마지막 돌일 때  철수가 밟을 수 있는 돌의 최대 개수 주의할 점dp[n-1]에 최댓값이 저장되지 않는다. 따라서 최댓값을 따로 저장하여 dp 배열의 값을 구할 때마다 최댓값을 업데이트해야 한다. 로직1. 돌의 개수 n을 입력받는다.2. 돌의 높이를 저장할 int[] stones 배열과, int[] dp 배열을 선언한다. 둘 다 크기는 n만큼 할당한다.3. 돌의..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.www.acmicpc.net풀이반복적인 재귀 호출을 방지하기 위해, w(a, b, c)의 반환값을 저장하는 3차원 dp 배열을 사용한다.이 때 -50 ≤ a, b, c ≤ 50 이므로, 인덱스를 0부터 100까지 사용하기 위해 배열의 크기를 101x101x101만큼 할당하여 w(a, b, c)의 반환값을 dp[a+50][b+50][c+50]에 저장한다.  로직1. int형 3차원 배열 dp를 선언하고, 크기를 101x101x101만..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구해야 한다. 아래층으로 내려올 때, 아래층에 있는 수에서 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 즉, 현재 위치를 기준으로 위층의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중 최댓값을 선택하여 그 수와 현재 위치의 수를 더한 값을 현재 위치의 배열에 저장하면 된다. 예시) 7 3 8..

https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net풀이상담을 할 수 있는 가능한 모든 경우를 구한 다음 그 중에서 최대 수익을 구해야 한다. 예시를 들어 설명하겠다. 먼저 1일에 상담을 한다고 가정했을 경우(현재 수익 10), 2, 3일은 할 수 없으므로 4일로 넘어간다. 4일에 상담을 한다고 가정하면(현재 수익 30), 5일로 넘어가고 또 이때 5일에 상담을 한다고 가정하면(현재 수익 45), 7일로 넘어간다. 7일에는 상담을 할 수 없으므로 총 수익은 45가 된다.총 수익을 구한 다음 가장 최근 분기였던 5일째로 돌아간다. 5일에 상담을 하지 않는다고 가정하면(현재 수익 30), 6일..