본문 바로가기

ALGORITHM

 (212)
백준 5585 거스름돈 (Java) 1. 문제 링크 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 그리디(탐욕) 알고리즘의 대표적인 문제이다. 1000엔 중 물건 가격을 뺀 잔돈을 구한 후 거스름돈의 개수가 가장 적게 나와야 한다. 반복문을 돌릴 때, 배열의 값보다 큰거나 같은 경우에는 빼고 아닐 경우에는 배열의 다음 값으로 넘어가도록 했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; public ..
백준 1085 직사각형에서 탈출 (Java) 1. 문제 링크 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 직사각형의 경계선까지의 거리를 구하는 문제이다. 그래서 주어진 입력과 꼭짓점의 x좌표 y좌표 사이와의 거리를 각각 구하면 된다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; public class Main { public static void main(Stri..
백준 1436 영화감독 숌 (Java) 1. 문제 링크 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 몇번째로 666이 포함된 숫자인지 찾는 문제이다. count가 입력받은 숫자와 같아질때까지 반복문을 돌린다. 666부터 시작해 숫자를 크게 만들면서 "666"이 포함된 문자열인지 확인했다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; public class Main { publ..
백준 1009 분산처리 (Java) 1. 문제 링크 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 컴퓨터 10대로 a^b개의 데이터를 처리하는 문제이다. a와 b의 값이 커질수록 계산이 느려지고 시간 초과가 발생할 것 같았다. 그래서 a^b를 하되 10(컴퓨터 개수)으로 나눈 한자리 수만 남겨서 곱셈을 이어나갔다. 계산 결과를 출력하면 된다. 여기서 나머지가 0인 경우가 있는데 컴퓨터는 1~10대이기에 10으로 출력했다. 4. 코드 import java.io.BufferedReader; import java.io..
백준 1152 단어의 개수 (Java) 1. 문제 링크 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 공백 기준으로 단어의 개수를 세는 코드를 작성하면 된다. 전체 입력의 앞뒤 공백을 trim()으로 제거한 문자열의 길이와 그 문자열에서 replace()로 공백을 모두 없앤 문자열의 길이의 차이 +1이 단어의 개수라고 생각했다. 하지만 82%? 86%정도에서 틀렸습니다를 만났다. 그 이유를 찾아보니까 공백만 입력될 경우에도 1이 출력되고 있었다. 그 부분을 수정해서 제출하니까 성공했다. 4. 코드 i..
백준 1546 평균 (Java) 1. 문제 링크 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 문제에 적혀있는 공식을 이용하면 된다. 그러나 여기서 중요한 점은 정수가 부정확하다는 점이다. 소수점이 있는 계산을 해야 하는데 int로 계산을 할 경우 예상과 다른 결과가 자주 나오기 때문에 정수를 실수로 바꾸는 과정이 필요하다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayLi..
백준 3052 나머지 (Java) 1. 문제 링크 3052번: 나머지 각 수를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 6개가 있다. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 ArrayList를 만들어서 계산 후 나머지를 추가한다. 리스트에 해당 나머지가 존재하는지 확인하고 없는 경우에만 넣어서 별도의 계산 없이 서로 다른 나머지 값의 수를 구한다. 4. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.uti..
백준 2869 달팽이는 올라가고 싶다 (Java) 1. 문제 링크 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 처음에는 반복문을 이용해서 A만큼 더하고, V가 넘었는지 확인하고, B만큼 뺐다. 그러나 시간초과라는 결과가 나왔다. 0.15초의 시간 제한이 있어서 반복 횟수가 늘어날수록 시간이 늘어났을 것이다. 반복문을 빼고 풀 방법을 생각하다 식으로 풀자고 생각했다. 마지막날 올라간 상태에서 끝이 난다는 가정하에 올라가야 하는 길이는 V-B / 하루동안 올라가는 길이인 A-B로 생각했다. V-B로 계산했다 나머지가 발생한 경우는 A-B보다 작은 길이가 남았다는 것으로 하루를..

티스토리툴바