알고리즘 문제풀이/백준 158

#9742 : 순열

풀이방법 사용된 것: 백트래킹 2022.05.10 백트래킹 문제이다. 아래의 정답 코드는 가지치기 없이 모든 경우의 수를 다 검사하도록 하였고 이렇게 해도 시간초과가 나지 않기 때문에 브루트포스 알고리즘 문제라고도 할 수 있다. 가능한 모든 순열을 만들면서, 새 순열이 만들어질 때마다 하나씩 세어준다. 세다가 그 숫자가 문제에서 주어진 번호(N)에 도달하면 그 번호의 순열을 출력 문자열에 추가하면 된다. 주어지는 글자들이 사전순으로 주어지므로, 입력 문자열의 앞에 있는 글자부터 하나씩 순서대로 순열에 추가하는 식으로 순열을 만들면 된다. 그럼 결과물인 순열들도 자연스럽게 사전순으로 앞에 있는 것부터 순서대로 도출된다. "No permutation"을 출력해야 하는 유일한 경우는 바로 문제에서 주어진 번호..

#2160 : 그림 비교

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.10 다 비교하면 된다. 알고리즘은 다음과 같다. 일단 그림 정보를 읽어온다. 그림의 색이 두 가지 뿐이므로 boolean 배열로 저장했다. 그 다음 비교를 한다. 필요한 변수는 min, a, b이다. int형 변수 min을 선언하고, 35보다 큰 수로 초기화한다. 정답에 해당하는 두 그림의 번호를 저장할 int형 변수 a와 b를 선언하고, 음수로 초기화한다. 그리고 가능한 모든 쌍에 대하여 다음의 과정을 반복한다. 두 그림을 선택한다. 두 그림을 비교하여, 서로 다른 칸의 개수를 센다. 서로 다른 칸의 개수를 담은 변수를 temp라 하겠다. min과 temp를 비교한다. min보다 temp가 작다면 min의 값을 temp로 업데이트하고, 방금 센 ..

#1037 : 약수

풀이방법 사용된 것: 정렬 수학 2022.05.07 정수 N의 값은 N의 가장 작은 1이 아닌 약수와 N의 가장 큰 본인이 아닌 약수를 곱한 것과 동일하다. 주어지는 약수들을 모두 읽어온 다음, 그 중에서 가장 작은 것과 큰 것을 곱한 값을 화면에 출력하면 된다. 코드 Java(2022.05.07) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{..

#11651 : 좌표 정렬하기 2

풀이방법 사용된 것: 정렬 Comparator Overriding 2022.05.04 Comparator를 오버라이드하여 정렬하면 된다. ▼Comparator Overriding하는 법 자바에서 내 마음대로 정렬하기: Comparator Overriding 기본 데이터타입이 아닌 객체(Object)를 정렬해야 할 때가 있다. 또한, 자바에서 기본으로 제공해주는 정렬함수로는 수행하기 힘든 복잡한 방식/기준의 정렬이 필요할 때도 있다. 백준 #1931 회의실 blowupmomo.tistory.com 코드 Java(2022.05.04) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..

#14928 : 큰 수 (BIG)

풀이방법 사용된 것: 수학 2022.05.03 오늘 새벽에 갑자기 올 솔브 배경이 가지고 싶어져서 가장 쉽고 문제 수도 적은 편인 브론즈 5 레벨 문제를 모두 푸는 켠왕을 시작했다. 방금 막 완료했다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ휴학하니까 별 뻘짓을 다 한다. 브론즈 5 쯤이야 껌이라고 생각했는데 50문제 넘게 풀다 보니 꽤 오래 걸렸다. 그리고 나름 새롭게 알게 된 것들도 있다. 난이도를 버린 대신 유머를 택한 나사 빠진 문제들이 많아서 재미있었다. 아무튼 이 글을 쓰는 것은 배경 얻은 날을 기록하기 위해서이기도 하지만 밤새 푼 브론즈 5 문제들 중 적어둘 만 한 문제가 하나 있기 때문이다. 14928번 문제는 큰 수의 나머지를 구하는 문제인데, BigInteger를 사용하면 시간초과가 난다. BigInteger..

#1436 : 영화감독 숌

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.03 1번째부터 10000번째까지의 종말의 수를 모두 미리 찾아두고, 그 중에서 입력값에 알맞은 수를 골라 출력하면 된다. 666부터 시작하여 모든 정수를 점검한다. 해당 수가 종말의 수라면 배열에 저장한다. 배열에 10000번째 종말의 수가 저장되면 점검을 종료한다. 입력값을 N이라 할 때, 배열에 N번째로 저장된 수를 화면에 출력하면 된다. 코드 Java(2022.05.03) import java.util.Scanner; public class Main { public static void main(String[] args){ // TODO Auto-generated method stub Scanner sc = new Scanner(System...

#7568 : 덩치

풀이방법 사용된 것: 브루트포스 알고리즘 2022.05.03 모든 사람에 대하여, 본인보다 몸무게도 무겁고 키도 큰 사람의 수를 일일이 세어주면 된다. 코드 Java(2022.05.03) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStre..

#1193 : 분수찾기

풀이방법 사용된 것: 수학 2022.05.01 가장 왼쪽 위의 대각선을 첫 번째 대각선이라 하고 오른쪽 아래로 갈수록 2, 3, 4, ... 번째 대각선이라 하자. 입력값으로 N이 주어진다. N번째 수가 몇 번째 대각선에 속하는지를 먼저 구하고, 그 대각선 내에서 몇 번째의 수인지를 구하면 된다. 이 두 가지만 알면 분수를 정확하게 구할 수 있다. 몇 번째 대각선에 속하는지 구하는 방법은 다음과 같다. 1번째 대각선부터 k번째 대각선까지에 속하는 분수의 개수는 1부터 k까지의 정수를 더한 것과 같다. 따라서, 1부터 k까지 더했을 때의 합이 N보다 크거나 같은 가장 작은 k를 찾으면 된다. N은 이 k번째 대각선에 속한다. k번째 대각선 내에서 몇 번째의 수인지를 구하는 법은 다음과 같다. 1~k의 정수..

#2869 : 달팽이는 올라가고 싶다

풀이방법 사용된 것: 수학 2022.05.01 딱 한 문장짜리 식으로 답을 구해야 하는 문제이다. 반복문이나 조건문 같은 것을 쓰면 높은 확률로 시간초과가 발생한다. 2022.04.27 2023년 2월 6일에 시간초과 기준이 바뀌어, 조건문을 사용해도 시간초과가 발생하지 않게 되었다. 그래서, 2022년 4월 27일에 제출했다가 시간초과를 받았으나 재채점 후 정답 처리가 된 조건문 코드를 하단에 정답 코드로 추가하였다. 반복문을 사용한 코드는 여전히 시간초과를 받는다. 코드 Java(2022.05.01) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

#13335 : 트럭

풀이방법 사용된 것: Queue 2022.04.30 2개의 큐를 사용하여 푸는 문제이다. 다리에 아직 올라가지 않은 트럭들을 저장하는 Queue trucks 다리 위의 상태를 저장하는 Queue bridge 이렇게 2개를 사용하였다. trucks의 각 요소는 한 대의 트럭마다 할당된다. 각각 해당 트럭의 무게를 저장한다. bridge의 각 요소는 하나의 단위길이마다 할당된다. 각각 해당 단위길이에 실린 무게를 저장한다. 백준 문제 페이지의 1번 예제의 경우에 위 2개 큐의 초기상태는 다음과 같다. 1번 예제의 입력값: 4 2 10 7 4 5 6 trucks의 초기 상태는 다음과 같다. 7 4 5 6 bridge의 초기 상태는 다음과 같다. 아직 아무 트럭도 다리 위에 올라가지 않았으므로 두 개의 단위길이..