Coding Test

[BOJ/JAVA] 16958번: 텔레포트

16958번: 텔레포트https://www.acmicpc.net/problem/16958키워드2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.구현두 도시 간 거리를 전부 계산하여 cityMatrix에 저장한다.만약 두 도시가 특별한 도시라면 T와 비교하여 더 작은 시간을 저장한다.플로이드-워셜 알고리즘을 이용하여 최소 이동 시간을 구하자.코드import java.io.BufferedRead..

[BOJ/JAVA] 1339번: 단어 수학

1339번: 단어 수학https://www.acmicpc.net/problem/1339키워드단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램구현각 자릿수의 가중치만큼을 계산해서 더해준다.N개의 단어라고해서 알파벳 A부터 Z까지의 알파벳을 전부 사용하는 것이 아니다.두 개 이상의 알파벳이 같은 숫자로 바뀌면 안되므로 입력에서 10종류 이하의 알파벳 단어만 주어질 것이다.→ Map을 이용하여 사용된 알파벳의 Key, 알파벳 가중치 Value를 저장한다.각 자릿수의 ..

[BOJ/JAVA] 23559번: 밥

23559번: 밥https://www.acmicpc.net/problem/23559키워드제주대 학생회관 식당에는 두 개의 메뉴가 있다.코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.NNN일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다.준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.준원이는 NNN일간 학식에 총 XXX원 이하를 써야 한다.고른 메뉴의 맛의 합을 최대화 해주자!구현일단 무조건 더 맛있는 메뉴를 고른다.이후 금액에 맞게끔 1,000원 짜리 메뉴로 바꾸었을 때 차이가 가장 적은 메뉴부터 교체해 나간다. boolean is5000[][i] 번째 고른 메뉴가 5000원 짜리 메뉴인가?더 맛..

[BOJ/JAVA] 27313번: 효율적인 애니메이션 감상

27313번: 효율적인 애니메이션 감상 https://www.acmicpc.net/problem/27313 키워드 애니메이션을 최대 M M M시간 동안만 보기로 했다. 한별이는 애니메이션을 동시에 최대 K K K개씩 묶어서 보기로 했는데, 한별이가 동시에 애니메이션을 보는 방법은 다음과 같다. 애니메이션을 보고 있지 않은 상태에서, 한별이는 아직 보지 않은 애니메이션 중 K K K개 이하의 애니메이션을 동시에 보기 시작한다. 애니메이션을 보고 있는 도중에는 새로운 애니메이션을 보기 시작할 수 없다. 이로 인해, 한별이는 보기 시작한 애니메이션 중에서 가장 긴 애니메이션이 끝날 때까지 다른 애니메이션을 보기 시작할 수 없다. 한별이는 애니메이션 시청의 달인이기 때문에 애니메이션이 끝남과 동시에 새로운 애니..

[BOJ/JAVA] 1744번: 수 묶기

1744번: 수 묶기https://www.acmicpc.net/problem/1744키워드길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다.수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다.수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.구현양수의 경우 큰 것 끼리 곱하면 더욱 커지므로 무조건 묶어준다.음수의 경우 작은 것 끼리 곱하면 더욱 커지므로 무조건 묶어준다.1의 경우 곱하면 더 작아지므로 더해준다.음수의 갯수가 홀수개 이고, 0이 존재한다면 가장 큰 음수와 0을 묶어준다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

[BOJ/JAVA] 1198번: 삼각형으로 자르기

1198번: 삼각형으로 자르기https://www.acmicpc.net/problem/1198키워드볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.구현문제에서는 삼각형을 계속 제거해 나갔지만 결국은 볼록 다각형의 3점으로 만들 수 있는 삼각형 넓이의 최댓값과 동일한 문제이다.N개의 점에서 3개를 선택하여 해당 삼각형의 넓이의 최댓값을 ..

[BOJ/JAVA] 1711번: 직각삼각형

1711번: 직각삼각형https://www.acmicpc.net/problem/1711키워드2차원 평면에 N개의 점이 주어져 있다. 이 중에서 세 점을 골랐을 때, 직각삼각형이 몇 개나 있는지를 구하는 프로그램을 작성하시오.구현한 점을 기준으로 다른 두 점을 향한 벡터의 내적이 0이면 직각임을 이용한다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class java_..

[BOJ/JAVA] 11758번: CCW

11758번: CCWhttps://www.acmicpc.net/problem/11758키워드2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.구현P1P2 벡터와 P2P3 벡터의 외적을 이용하여 계산한다.두 벡터의 외적이 0이면 일직선이다.두 벡터의 외적이 양수면 시계방향이다.두 벡터의 외적이 음수면 반시계방향이다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class java_11758 { s..

[BOJ/JAVA] 1701번: Cubeditor

1701번: Cubeditorhttps://www.acmicpc.net/problem/1701키워드어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램구현kmp 알고리즘을 이용하여 구현한다.문자열 알고리즘용어 정리 |S| 문자열 S의 길이 S = “abcde” 라면 |S| = 5 S[i] (0 ≤ i < |S|) 문자열 S의 i번 글자 S = “abcde” 라면 S[3] = d S[i…j] 문자열 S[i] 부터 S[j] 까지 부분 문자열 S = “abcde” 라면 S[1…3] = bcd S[…a] 문자열 S[0] 부터 S[a] 까지 부분 문자열 S = “abcde” 라면 S[…3] = abcd S[b…] 문자열 S[b] 부..

[BOJ/JAVA] 1599번: 민식어

1599번: 민식어https://www.acmicpc.net/problem/1599키워드민식어는 a b k d e g h i l m n ng o p r s t u w y의 순서ng는 n과 o사이에 오는 하나의 알파벳민식어의 순서대로 정렬하는 프로그램구현다음 3가지를 구현하면 된다.민식어의 우선순위를 처리하는 방법ng를 판단하는 방법문자열을 특정 조건으로 정렬하는 방법 1. 민식어의 우선순위 처리하는 방법final static Map minsikMap민식어는 a b k d e g h i l m n ng o p r s t u w y의 순서대로 우선순위를 가진다.따라서 해당 문자가 몇 번째 우선순위인지 map에 저장해두도록 하자ng는 문자열이므로 -라는 문자로 치환하여 저장하자.2. ng를 판단하는 방법민식어..