Melody Coding

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..

Silver I문제(출처: https://www.acmicpc.net/problem/12026) 문제 풀이  이중 for문을 사용하여 보도블록을 전체 탐색한다. B -> O -> J 순서로 확인하면서 최솟값을 찾는다.  my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class _12026_ { // BOJ 거리 public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));..

Silver I문제(출처: https://www.acmicpc.net/problem/2529) 문제 풀이  만들 수 있는 모든 조합을 구하면서 부등호에 만족하는 값만 다음 값으로 넘겨준다.  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 _2529_ { // 부등호 static int num[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; stat..

Silver I문제(출처: https://www.acmicpc.net/problem/1890) 문제 풀이  게임 판의 정보를 저장하는 배열, 이동 위치를 표시하는 배열, 경로 수를 구하는 배열 총 3개의 배열을 사용해서 문제를 해결했다.  만약 문제에서 주어진 예제로 설명해 보자.42 3 3 11 2 1 31 2 3 13 1 1 0와 같이 예제가 주어졌다면 이동 위치를 표시하는 배열은 다음과 같다. 경로 수를 구하는 배열은 다음과 같다. 각 경로는 같은 이동 번호인 경우가 아니라면 따로 관리한다. 위에서 4번 이동하여 오른쪽 아래로 오는 경우가 2가지였고 5번 이동해서 오른쪽 아래 도착하는 경우가 1가지이므로 먼저 도착한 경우의 수를 따로 저장해 두고 1로 저장한다. 반복문을 사용해서 이동 번호로 탐색하..