문제 분석1번 헛간에서 N번 헛간까지 가는 동안 만나는 모든 소에게 여물을 줘야 함가능한 적은 수의 소를 만나고, 최소한의 여물을 주면서 N번 헛간에 도착할 수 있는 경로 찾아야 함최소 합의 여물 구하기 의사 결정우선순위 큐(최소 힙)을 사용해서 최소 여물 수를 먼저 계산할 수 있도록 했습니다.연결된 경로와 가중치(여물)을 저장하기 위해 ArrayList arr 배열을 인접 리스트로 사용하여 양방향 간선 정보를 저장했습니다.다익스트라 알고리즘을 사용하여 출발지에서 목적지까지 필요한 최소 여물의 합을 구했습니다. 코드 구현1. Node 객체 선언이동할 노드와 가중치(여물의 양)을 저장할 Node 객체를 선언했습니다. 우선순위 큐에서 여물의 양이 더 적은 경로를 먼저 처리하기 위해, Comparable 인터..

문제 분석친구 관계를 통해서 회장 후보를 선정하기각 회원은 다른 모든 회원들과의 친구 관계를 통해 점수를 가지게 되며가장 적은 점수를 가진 회원이 회장 후보가 됨회장의 점수와 후보의 수, 회장 후보 목록을 출력하기 의사 결정친구 관계는 바로 연결된 친구 뿐만 아니라 친구의 친구까지 포함되기 때문에 양방향 간선을 사용했습니다.A가 B의 친구면, B도 A의 친구 입니다.회원 간의 관계를 인접 행렬로 사용하였고, 플로이드-워셜 알고리즘을 통해 정점 사이의 최단 경로를 구했습니다. 코드 구현1. 회원의 수 입력 및 인접 행렬 선언, 초기화회원 수를 입력 받고, 이 수에 맞게 인접 행렬을 선언했습니다.최대 회원 수는 50명이고, 초기값을 무한대로 설정하기 위해 51로 설정했습니다.자기 자신과의 경로는 0으로 초기..

문제 분석직선의 고속도로에 원점을 기점으로 N개의 센서가 설치되어 있음N개의 센서가 적어도 1개의 집중국과 통신되어야 하고, 최대 K개의 집중국을 세울 수 있음각 집중국의 수신 가능 영역 길이(0 이상) 합의 최소값을 구하기 의사 결정K개의 집중국을 세우면, 집중국 사이의 빈공간이 K-1개가 생깁니다.센서 사이의 거리를 내림차순하여 정렬합니다.큰 거리부터 K-1개의 공간을 제외하고, 나머지 공간을 모두 더하는 방식을 사용했습니다. 코드 구현1. 센서와 집중국의 개수, 센서 좌표 입력 받기각 센서의 위치는 배열에 저장했습니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(..

문제 분석2원과 5원으로만 거스름돈을 줄 때, 최소로 거슬러 줄 수 있는 개수 구하기만약, 거슬러 줄 수 없다면 -1 출력 의사 결정주어진 거스름돈 액수가 5로 나누어질 때까지 2씩 빼는 방식을 사용했습니다. 코드 구현1. 거스름돈 액수 입력받기 StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine());  2. 거스름돈 액수 계산 및 결과 출력입력받은 num이 먼저 5로 나누어떨어지는지 확인했습니다.5의 배수면 나눈 값을 바로 결과로 출력했습니다. 5의 배수가 아니면, while문..

문제 분석아이들의 번호 순서가 뒤바뀐 상태에서 오름차순으로 정렬하려고 할 때위치를 옮기는 아이들의 최소 횟수 구하기 의사 결정번호가 뒤바뀐 상태에서 LIS(최장 증가 부분 수열)의 갯수를 구하고, 전체 아이들 수에서 횟수를 빼는 방식을 사용했습니다. 코드 구현1. 아이들의 수 입력, 배열에 번호 순서 저장번호가 증가하는 순서대로 횟수를 저장하기 위해 배열을 선언하고, count 배열의 모든 인덱스를 1로 초기화 했습니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] a = new int[N]; int[] count..

문제 분석앞에 있는 상자 크기가 뒤에 있는 상자 크기보다 작으면, 뒤에 있는 상자 안에 앞 상자를 넣을 수 있음한번에 넣을 수 있는 최대 상자 갯수를 출력하기상자 순서는 변경할 수 없다. 의사 결정상자의 크기를 비교하면서 한번에 넣을 수 있는 상자 갯수를 저장하고, 갯수의 가장 큰 값을 출력하는 방식을 사용했습니다. 코드 구현1. 상자의 갯수와 크기 입력, 배열에 상자 크기 저장 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] a = new int[N+1]; StringTokenizer st = new StringTokenize..

문제 분석크기가 무한대인 정사각형 모눈종이에 소용돌이 모양의 반시계 방향으로 양의 정수를 채움제시된 범위에 맞는 소용돌이 이쁘게 출력하기 의사 결정처음에는 이중 배열을 구현하여 값을 채워넣고, 제시한 범위만 잘라서 출력하도록 했지만 메모리 초과로 실패했습니다.-5 000 ≤ r1, c1, r2, c2 ≤ 5,000 으로 좌표 값이 크게 설정되면 이중 배열이 너무 커지기 때문에 메모리 초과가 발생한 것으로 추측됩니다.각 좌표의 값을 소용돌이 규칙에 따라 계산하고, 제시된 이중 배열 범위에 추가하여 출력하는 방식을 사용했습니다. 코드 구현1. 각 좌표 (R1, C1, R2, C2) 입력공백을 기준으로 split으로 잘라 각 자표를 변수에 저장했습니다. BufferedReader br = new Buffer..

https://www.acmicpc.net/problem/2579재귀 함수를 사용해 풀수도 있지만, 동적 계획법(DP)를 사용해 풀었습니다.풀이방법1. 점화식의 형태와 의미는 DP[N] = N개의 계단에서 최대 점수로 도출하였습니다.최대값을 찾는 문제이기 때문에 핵심 점화식에서는 Math.max 함수가 있다는 것을 알 수 있습니다. 이를 토대로 계단이 1개 ~ 5개일 경우, 하드 코딩으로 작성해봅니다.DP[1] = step[1]DP[2] = step[1] + step[2]DP[3] = step[1] + step[3]          = step[2] + step[3] 이므로 max(step[1]+step[3] , step[2] + step[3]) 이다.DP[4] = step[1] + step[2] + s..

https://www.acmicpc.net/problem/1074분할 정복, 재귀 함수를 사용한 문제이다.우선, Z가 지나온 방향으로 분석을 해보고자 했고, 대략적인 패턴은 발견했지만 이를 어떻게 구현해야 할지 감이 잡히지 않았습니다. 가장 아래 걸어둔 링크를 통해 해당 문제 패턴을 파악하였습니다.  풀이 방법1. 배열을 사분면으로 나누고, 입력 받은 r, c가 몇 번째 사분면에 속하는지 확인합니다.2. 재귀를 호출할 때마다 현재 r,c의 위치에 따라 앞 사분면에서 몇 번 방문했는지 더 하는 변수 count를 선언 합니다.3. find 메소드를 정의하고, 매개변수로 한 변의 사이즈 size와 타겟 위치 인덱스 r, c를 넘깁니다. 3-1. r과 c가 1사분면에 속한다면, 아무 곳도 방문하지 않았기 때문에..

https://www.acmicpc.net/problem/14891시뮬레이션 문제 이다.풀이 방법1. 톱니바퀴의 극을 입력 받는다. 문자로 입력 받으면 아스키 코드로 출력되기 때문에 (int) input.charAt()-48를 사용하여 정수로 변환한다.2. 특정 톱니바퀴(3번)의 우측 톱니바퀴(4번) 회전 정보를 확인한다. 극이 다르면 현재 톱니바퀴 방향의 반대 방향으로 설정한다. 우측과 마찬가지로 좌측 톱니바퀴(2번, 1번) 회정 정보를 확인한다. 좌측 톱니바퀴는 2개이기 때문에 회전 전파가 이루어져야 한다.3. 회전 정보에 맞춰서 톱니바퀴를 방향에 맞춰 회전 시킨다.4. 각 톱니바퀴에 맞는 점수를 계산하여 출력한다. 정답 코드import java.io.BufferedReader;import java...