본문 바로가기

분류 전체보기

(10)
[백준] 1059번 : 좋은구간 [Java] https://www.acmicpc.net/problem/1059 1059번: 좋은 구간 [9, 10], [9, 11], [9, 12], [10, 11], [10, 12] www.acmicpc.net ● 문제 ● 접근 방법 low 와 high 로 점점 좁혀가며 구해보자. S집합은 오름차순으로 정렬하여 계산하기 쉽게 만들자. 예를 들어 S집합을 [1, 5, 9, 40, 100], n은 31로 정하자. 그런데 S[0]은 n보다 작다. 한마디로 중간값이 없을 수 밖에 없는 수. 그러므로 1은 버리고 low와 high 를 초기화 시켜주는 것이다. 그렇게 1,5 9 는 버려지게 되는 것이다. 이제 S[3] > n 보다 크다. 그럼 low는 S[2] + 1 부터 S[3] - 1 까지 즉 low는 9 + 1 = 10..
[백준] 1032번 : 명령 프롬프트 [Java] https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net ● 문제 ● 접근 방법 String 배열의 크기를 n만큼으로 만들어준다. 다행히도 모든 n개의 글자의 길이는 같아서, 쉽게 문제 풀이가 가능하다. String 배열을 cap이라고 두고, answer을 공백의 문자로 설정하자. cap의 크기는 n이고 모든 글자수는 같으므로 cap[0]을 기준으로 잡고, cap[1~(n-1)] 까지 비교하면 된다. for문으로 cap[i] 주소에 있는 문자열에 ..
[백준] 2501번 : 약수 구하기 [Java] https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net ● 문제 ● 접근 방법 n과 k의 범위가 크지 않아서 단순 반복으로 판단하여도 쉽게 해결되는 문제. n을 1~n로 나눈 나머지가 0일때 cnt를 1 카운트 시켜주고, cnt가 k일때 출력해주면 끝나는 쉬운 문제. ● 문제 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { int cnt = 0; int answer = 0; //입력 Scanner sc = new ..
[백준] 1011번 : Fly me to the Alpha Centauri [Java] https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net ● 문제 ● 접근 방법 k(n) = k(n-1) - 1 or k(n-1) or k(n-1) + 1 이다. 한마디로 다음 거리는 이전 거리보다 ±1 또는 같다. 현재위치 x와 목표위치 y와의 거리는 y - x이다. 첫 이동과 마지막 이동은 무조건 1이다. 다음 표와 같이 y-x의 거리에서 나올 수 있는 최대 이동 거리는 거리의 제곱근 [내림] 이다. 이 ..
[백준] 1009번 : 분산처리 [Java] https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net ● 문제 ● 접근 방법 문제를 간단하게 풀어쓰면 a 를 b번 제곱하라는 문제이다. 하지만 a에 b를 계속 곱하기만 하면 숫자가 너무 커지니, 1의 자리수만 뽑아 수를 줄인다. ● 문제 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { // 입력 Scanner sc = new Scanner(Syste..
[백준] 1008번 : A/B [Java] https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net ● 문제 ● 접근 방법 딱히 다른것을 설명할 것이 없이 입력받은 a와 b를 나누라는 문제. 하지만 상대오차가 10^-9승 이라는 조건이 있다. 물론 자바는 double로 소수 15자리 까지 표현하여 오차범위에 들어 그냥 출력해도 문제없다. 그래도 9자리에서 끊어주기 위해 String.format을 이용하자. ● 문제 풀이 import java.util.Scanner; public class Main{ public static void main(String[] args) { //입력 Scanner sc = new Sc..
[백준] 1003번 : 피보나치 함수 [Java] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ● 문제 ● 접근 방법 문제만 보면 어려워 보이는 문제. 피보나치 수열과 0, 1 개수의 상관 관계만 찾으면 문제의 난이도는 쉬워진다. 그럼 여기서 0,1 과 피보나치 수열의 상관 관계를 찾아보자. 0의 출력횟수는 dp[n-1] 인 것이 보이는가? 1의 출력횟수는 dp[n] 을 그대로 가져왔다. 이 문제는 다이나믹 문제인 것이다. ● 문제 풀이 import java.util.Scanner; public class Main{ public static void main(String[] args) ..
[백준] 1002번 : 터렛 [Java] https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net ● 문제 ● 접근 방법 조규현위 위치 (x1, y1)와 백승환의 위치 (x2, y2)가 주어지며 r1은 조규현의 위치로 부터 류재명까지의 거리를 나타내며, r2는 백승환의 위치로 부터 류재명까지의 거리를 나타낸다. 이때 류재명이 존재 가능한 위치를 찾는 문제이다. 이때, 조규현, 백승환의 위치 정보로 알 수 있는 류재명의 위치의 경우는 다음과 같다. 파란 점 : 조규현 위치 빨간 점 : 백승환 위치 초록 점 : 류재명 존재 가능 위치 모든 케이스를 ..