Melody Coding

Gold V문제(출처: https://www.acmicpc.net/problem/17609) 문제 풀이  문자열의 맨 처음과 끝을 시작으로 중간까지 보면서 회문인지 확인한다.  * 왼쪽 문자를 제거했을 때, 오른쪽 문자를 제거했을 때 둘 다 회문일 가능성이 있다면 두 가지 경우 다 확인해야 한다.   my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;public class _17609_ { // 회문 static String str; static bo..

Gold V문제(출처: https://www.acmicpc.net/problem/13398) 문제 풀이  처음에는 수열 값 중에서 음수 중 가장 작은 값을 제거하는 방법으로 구현했다. 하지만 이렇게 구현할 경우 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구할 수 없다.  그래서 두 번째 방법으로는 모든 수를 한 번씩 제거하는 경우로 배열을 n x n 크기로 만들어서 구현했다. 하지만 이 경우에는 n의 범위가 1 이상 100000 이하이므로 메모리 초과가 발생했다. 마지막으로 구현한 방법은 배열을 2 x n 크기로 만들어 0번째 행은 수를 제거하지 않은 경우, 1번째 행은 수를 하나 제거한 경우로 구현했다.  my solution (Java)import java.io.Buffered..

Gold V문제(출처: https://www.acmicpc.net/problem/5582) 문제 풀이  배열 2개를 사용해서 공통부분 문자열을 구한다. 만약 abcd와 bacd라면 아래와 같이 만들어지도록 구현한다. abcdb0100a1000c0010d0002   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class _5582_ { // 공통 부분 문자열 public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new Inp..

Silver I문제(출처: https://www.acmicpc.net/problem/20529) 문제 풀이  조합을 사용하여 3명의 학생의 MBTI 성격 유형을 뽑아 가장 가까운 세 사람의 심리적 거리를 구한다. 조합으로만 문제를 구현할 경우 시간초과가 발생한다. 시간을 줄일 방법을 몰라 찾아보니 비둘기집 원리를 사용하는 것이었다. 비둘기집 원리를 사용하면 MBTI가 총 16개 이므로 만약 사람 수가 32명이라면 똑같은 MBTI가 2명씩 있을 수 있으며 사람 수가 32명보다 많다면 똑같은 MBTI가 무조건 3명이 있게 된다. 그럼 가장 가까운 세 사람의 심리적 거리가 0이 되므로 사람 수가 32보다 크다면 조합을 구할 필요가 없다.   my solution (Java)import java.io.Buffe..

Silver I문제(출처: https://www.acmicpc.net/problem/16198) 문제 풀이  에너지를 구할 수 있는 모든 경우를 다 구하여 에너지의 최댓값을 구한다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class _16198_ { // 에너지 모으기 static int arr[], result; static boolean visited[]; public static void main(String[] args) throws IOException { Buffer..

Silver I문제(출처: https://www.acmicpc.net/problem/1189) 문제 풀이  dfs를 활용하여 거리가 k인 가짓수를 구한다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class _1189_ { // 컴백홈 static int result, k; static boolean visited[][]; static int dx[] = { -1, 1, 0, 0 }; static int dy[] = { 0, 0, -1, 1 }; public static void ..

Silver I문제(출처: https://www.acmicpc.net/problem/21937) 문제 풀이  B 작업을 하기 위해 바로 이전에 A 작업을 해야 한다면 작업 B를 하기 위해 먼저 해야 하는 일을 찾기 위해 거꾸로 저장한다. 그래프를 저장할 때 B에 A를 저장한다. 그 후 dfs를 사용하여 답을 구한다.    my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class _21937_ { // 작업 static ArrayList> li..

Silver I문제(출처: https://www.acmicpc.net/problem/1283) 문제 풀이  먼저 단어를 입력받으면서 단어의 첫 글자가 단축키인지 확인하여 단축키가 아니라면 단축키로 설정한다. 모든 단어의 첫 글자가 이미 단축키라면 왼쪽부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 설정한다.   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.ArrayList;import jav..

Silver I문제(출처: https://www.acmicpc.net/problem/1446) 문제 풀이  지름길을 ArrayLIst에 저장한 후 모든 길을 탐색하면서 지름길로 이동 가능하면 이동 후 최솟값을 찾는다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class _1446_ { // 지름길 public static void main(String[] args) throws IOException { BufferedReader b..

Silver I문제(출처: https://www.acmicpc.net/problem/4883) 문제 풀이  처음에는 가장 위쪽 가운데 정점에서부터 시작해서 Queue를 사용해서 이동하는 곳마다 저장하여 최소 비용을 구하도록 구현했다. 하지만 중복되는 위치가 있어서 그런지 시간초과가 발생했다. 삼각 그래프 각 정점에서 이동할 수 있는 위치는 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래 총 4가지 경우이다. 그러므로 정점을 위에서부터, 왼쪽에서 오른쪽으로 탐색해도 된다는 뜻이다. 왼쪽으로 이동할 수 없고, 위로 이동할 수 없기 때문이다. 또한, 비용의 제곱이 1,000,000이므로 비용이 음수일 수 도 있다는 뜻이므로 최소 비용을 구하는 배열의 초기값을 0으로 설정하면 정확한 답을 구할 수 없으므로 Intege..