Dogfootruler Kim

문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 및 소스코드 MST를 사용해서 최소 가중치로 그래프를 만들어 준 후, 가장 가중치가 큰 간선 하나를 빼면 유지비가 최소가 되는 두 마을을 만들 수 있다. 따라서 원래의 MST는 n-1번의 간선을 만들어줬다면, 이 문제는 n-2번의 간선만 만들어주면 된다. 크루스칼 알고리즘 사용 (320940kb, 1160ms) import java.io.Buffer..

풀이 및 소스코드 가중치가 위치에 따라서 다르기 때문에 BFS/DFS가 아닌 다익스트라를 사용했다. 먼저 가중치가 담길 d 배열을 Integer.max 값으로 초기화 해준 후, 대소비교를 해가면서 우선순위 큐에 넣어주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class Solution { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(ne..

풀이 및 소스코드 아래 링크 티스토리를 보고 해결했다 ! 한 번에 이해가 되니 보시길 ㅎㅎㅎ https://lovelyunsh.tistory.com/62 [SWEA] 5643 키순서 1. 문제 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo&categoryId=AWXQsLWKd5cDFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다.. lovelyunsh.tistory.com import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 및 소스코드 BFS로 탐색한다. 같은 좌표에 있더라도, 갖고 있는 키에 따라서 갈 수있고 없고가 결정된다. 따라서 방문표시하는 v 배열을 3차원으로 만들어준다. 여기서 키 방문체크는 비트마스킹을 사용한다. 키의 개수는 a~f 까지 총 6개이다. 따라서 v[n][m][1

문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 풀이 및 소스코드 4번 타자는 1번 선수로 고정시키고 그 외에는 순열으로 경우의 수를 구한 다음 스코어를 계산해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static ..

문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 및 소스코드 1. 조합으로 선거구 묶음 구하기 1개+n-1개, 2개+n-2개 이런식으로 나눠줌 for(int i=1;i

문제 https://www.acmicpc.net/problem/1755 1755번: 숫자놀이 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 www.acmicpc.net 풀이 및 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { p..

문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 및 소스코드 조합+구현 문제이다. 세 시간만에 풀었다 ㅠㅠ 오랜시간 푼 만큼 주석을 열심히 달았다. 설명은 주석으로 대신 하겠다 ㅠㅠㅠㅠㅠㅠㅠㅠ 지침...~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.u..