본문 바로가기

ALGORITHM

 (212)
백준 11050 이항 계수 1 (Java) 1. 문제 링크 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 이항계수를 구하는 공식은 n! / (k! * (n-k)!)이다. 그래서 분자와 분모에 공통되는 부분은 계산하지 않기 위해 N-K 값을 이용했다. N-K와 K 값 중 큰 값을 max로 나머지를 min으로 두고 풀었다. N부터 max까지 곱하고, min부터 1까지 나눈 값을 출력했다. 4. 코드 import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] a..
백준 1541 잃어버린 괄호 (Java) 1. 문제 링크 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 빼기 기준으로 문자열을 나눠서 각 문자열에서 더하기를 먼저 한다. 그러면 값을 뺄 때 더할 수 있는 값을 전부 더했기에 큰 값을 빼게 되는 것이다. 최종적으로 만들 수 있는 최솟값을 만들 수 있다. 4. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scan..
백준 1987 알파벳 (Java) 1. 문제 링크 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 입력받은 map을 dfs로 탐색한다. 알파벳은 boolean 배열을 이용해서 들렀는지 아닌지 확한다. 방향벡터를 이용해서 범위 안에 있을때 방문했던 위치인지 확인하고 재귀한다. 처음에 한 칸이 기본이니까 값을 세는 시작이 1이라는 점도 꼭 챙겨야 한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.In..
백준 1049 기타줄 (Java) 1. 문제 링크 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 기타줄의 패키지 가격은 배열에 저장하고, 낱개 가격은 제일 작은 가격만 저장한다. 최솟값은 각 패키지로 샀을 때의 가격마다 패키지로 사고 남은 만큼 낱개로 사는 가격으로 했다. 그렇게 구한 패키지를 샀을 경우의 최솟값과 낱개만으로 샀을 때의 가격을 비교해서 출력한다. 근데 다시 보니까 둘 다 최솟값만 구했으면 배열을 사용하지 않아도 되니까 더 좋을 것 같았다. 근데 유의미한 차이는 없더라...ㅎ 4. ..
백준 17135 캐슬 디펜스 (Java) 1. 문제 링크 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 궁수의 조합을 먼저 구하고 그 조합으로 dfs를 진행한다. 사정거리 안에 있는 적을 찾고 비교해서 최솟값을 계속 바꾼다. 최솟값이 있다면 boolean 배열의 값을 true로 한다. (이 배열은 같은 적을 공격할 경우를 대비해서 만들었다.) 모든 궁수가 공격할 적을 찾았다면 기존 배열인 map의 값을 0으로 바꾸고 count를 증가한다. 그러고 한 줄씩 아래로 내리고 count값이 크다면 값을 바꾼다. 다른 조합으로 ..
백준 1697 숨바꼭질 (Java) 1. 문제 링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 BFS를 이용해 문제를 풀었다. N과 K가 같을 경우 움직일 필요가 없으니 0을 출력하고 끝난다. 그 외의 경우에는 bfs() 함수로 넘어갔다. -1, +1, *1를 하면서 각 값이 범위 안에 들어가면 큐에 넣었다. 하나씩 큐에서 빼면서 값이 도착지점에 도착할 때까지 그 과정을 반복하면 된다. 4. 코드 import java.util.ArrayDeque; import java.u..
백준 2577 숫자의 개수 (Java) 1. 문제 링크 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 주어진 숫자를 곱해서 String으로 변환한다. 길이만큼 반복문을 돌면서 각 자리의 숫자를 배열의 인덱스로 해서 값을 +1 한다. 끝난 후 배열을 돌면서 배열의 값을 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader ..
백준 2606 바이러스 (Java) 1. 문제 링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 인접행렬을 이용해서 무향 그래프를 연결시켰다. 1번을 큐에 넣고 큐가 빌 때까지 반복한다. 큐에서 꺼낸 정점의 인접 정점들을 큐에 넣고 방문처리를 한다. 큐에 들어갔던 정점의 수를 함께 세고, 마지막에 1을 빼고 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ..

티스토리툴바