Melody Coding

Gold IV문제(출처: https://www.acmicpc.net/problem/3584) 문제 풀이 & 생각 dfs를 활용하여 공통 조상을 찾는다.  my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;public class _3584_ { // 가장 가까운 공통 조상 static int root[], result; static boolean visited[]; public static vo..

Gold IV문제(출처: https://www.acmicpc.net/problem/2036) 문제 풀이 & 생각 단순 조건 분기를 활용해서 해결할 수 있는 문제였다. (0과 1이 존재할 때 조건 분기를 놓치지 않아야 한다.) 반례 조건1) 1, 3이 있을 경우 1*3 2) -8,0과 같이 0이 있으며 음수가 1개 있다면 -8*0 > -8+0이다. 또한, 1,000,000이 넘지 않는 정수가 입력으로 주어지므로 int 범위가 벗어나므로 long형을 사용해야 한다.  my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;publ..

Silver V문제(출처: https://www.acmicpc.net/problem/1789) 문제 풀이 & 생각 n의 최댓값을 구하는 것이므로 1부터 시작해서 더했을 때 구하는 값 보다 크거나 같아지면 종료한다.만약 5를 구하는 것이면 1+2+3에서 1이 빠지면 된다. 문제를 풀 때 주의할 점은 자연수 범위가 int를 벗어나므로 long으로 선언해야 한다.    my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String args[]) throws IOException { Buff..

Gold III문제(출처: https://www.acmicpc.net/problem/17299) 문제 풀이 & 생각 17298 오큰수 문제에서 수열에 등장한 횟수만 추가로 구하니 문제를 쉽게 해결할 수 있었다. https://melody-coding.tistory.com/324 [Baekjoon] 17298_오큰수Gold IV문제(출처: https://www.acmicpc.net/problem/17298) 문제 풀이 & 생각 처음에는 이중 포문을 사용해서 구현했더니 시간초과가 발생했다. stack을 사용하여 시간초과를 해결할 수 있었다.현재 값과 다melody-coding.tistory.com    my solution (Java)import java.io.BufferedReader;import java..

Gold IV문제(출처: https://www.acmicpc.net/problem/17298) 문제 풀이 & 생각 처음에는 이중 포문을 사용해서 구현했더니 시간초과가 발생했다. stack을 사용하여 시간초과를 해결할 수 있었다.현재 값과 다음 값을 비교하여 다음 값이 크다면 오큰수 이므로 답을 출력하고 오큰수가 아니라면 stack에 넣어 큰 값이 올 때까지 기다리는 방법으로 구현했다.   my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import ..

Gold IV문제(출처: https://www.acmicpc.net/problem/3425) 문제 풀이 & 생각 stack을 사용해서 문제를 해결하며 예외 조건을 잘 구현해야 한다. 예외 조건1) POP, INV, DUP 일 때 stack이 비어있으면 ERROR이다.2) SWP 일 때 stack의 크기가 2보다 작으면 ERROR이다.3) ADD, SUB, MUL, DIV, MOD 일 때 stack의 크기가 2보다 작으면 ERROR이다.4) 각 연산이 1000000000보다 크면 ERROR이다.5) DIV와 MOD 일 때 0으로 나누는 경우는 ERROR이다.6) 최종 stack의 크기가 1이 아니면 ERROR이다.   my solution (Java)import java.io.BufferedReader;i..

Gold IV문제(출처: https://www.acmicpc.net/problem/14267) 문제 풀이 & 생각 직속 상사의 번호를 입력받으므로 이 정보를 이용해서 각 직원의 직속 부하를 저장해 둔다. 처음에는 직속 부하 정보를 저장해 둔 것을 이용해서 답을 구했지만 시간 초과가 발생했다.그 이유는 칭찬을 받을 때마다 dfs 함수를 호출해서 시간 초과가 발생했던 것이다.이것을 해결하기 위해 칭찬을 다 저장한 후 dfs 함수를 한 번 호출하여 구했더니 통과할 수 있었다.  시간초과 코드(Java)더보기import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamRe..

Gold IV문제(출처: https://www.acmicpc.net/problem/16562) 문제 풀이 & 생각 bfs 탐색을 통해 친구의 친구 중에서 최소 비용을 구한다.  my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _16562_ { // 친구비 static int f[], money; st..

Gold IV문제(출처: https://www.acmicpc.net/problem/1043) 문제 풀이 & 생각 파티 정보를 입력받으면서 파티 정보를 저장하며, 파티에 오는 사람들을 인접 리스트로 저장한다.그 후에 진실을 아는 사람을 기준으로 bfs 탐색을 통해 진실을 듣는 사람들을 판별한다. 인접리스트에는 만약 파티에 1 2 3이 온다면 (1,2) (1,3) (2,3)을 각각 저장한다.  my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.uti..

Gold IV문제(출처: https://www.acmicpc.net/problem/12893) 문제 풀이 & 생각 bfs를 사용해서 우호 관계와 적대 관계를 구분한다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _12893_ { // 적의 적 static ArrayList> arr; static boolean team[], visite..