본문 바로가기

백준114

[백준] 4134번 다음 소수 JAVA (자바) 풀이 문제 4134 (수학, 브루트포스)정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성   [입력]  :  첫째 줄에 테스트 케이스의 개수   :  정수 n ( 각 테스트 케이스는 한 줄 )       [출력] :  n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력    [참고]  소수 찾기 공식 2 ~ 제곱근까지 입력받은 수로 나눴을 때 나누어 떨어지지 않아야 소수!나누어 떨어진다면 입력받은 수에서 +1씩 올려 계산해보기 런타임 에러 피하기입력받은 숫자 n의 범위가 크기 때문에 long 타입으로 바꿔줄 것!  [코드] import java.io.*;import java.util.*;public class Main{ .. 2024. 5. 9.
[백준] 6603번 로또 JAVA (자바) 풀이 문제 6603번 (백트래킹)  :  {1, 2, ..., 49}에서 6개 택  :  k개(k>6) 골라 집합 S 만들어 6개의 조합 만들기   [입력] :  각 줄의 첫 번째 수는 k (6     (입력 마지막 줄 = 0)  [출력] :  각 테스트 케이스마다 경우의 수 출력 (사전 순 / 중복 금지)  :  각 테스트 케이스 사이에는 빈 줄 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(2) 문제 응용버전이다  마찬가지로 boolean이 필요없다 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에  굳이 .. 2024. 5. 4.
[백준] 15652번 N과 M(4) JAVA (자바) 풀이 문제 15652번 (백트래킹)  :  1부터 N까지 자연수 중에서 M개를 고른 수열 (중복선택 가능)  :  고른 수열은 비내림차순비내림차순 : A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK    (예) N = 3, M = 2 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1, 1 / 1, 2 / 1, 3 / 2, 2 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다   [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력   [과정]  탐색하자 → 브루트포스 / dfs →.. 2024. 5. 4.
[백준] 15650번 N과 M(2) JAVA (자바) 풀이 문제 15650번 (백트래킹)  :  자연수 N과 M이 주어졌을 때,    1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열 구하기  :  고른 수열은 오름차순        (예) N = 3, M = 2 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1, 2 / 1, 3 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다   [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 .. 2024. 5. 3.
[백준] 5568번 카드 놓기 JAVA (자바) 풀이 문제 5568  (백트래킹)  : 카드 n장 (4 ≤ n ≤ 10)   각 카드 1이상 99이하의 정수 : 카드 k장 (2 ≤ k ≤ 4) 선택 후 가로로 나란히 정수를 만들기 : 만들 수 있는 정수는 모두 몇 가지일까? [입력] : 첫째 줄에 n, 둘째 줄에 k: 셋째 줄 ~ n개 줄에는 카드에 적혀있는 수 [출력] : 만들 수 있는 카드 개수  [과정] 조합 중복 방지 vs 결과 중복 방지조합 중복 (백트래킹으로 해결)조합 중복 방지란 (1,1)이 아닌 (1,2)처럼 서로 다른 조합을 말한다 결과 중복 (hashset으로 해결)결과 중복 방지란 (1,2)와 (2,1)을 같은 값으로 처리하는 것을 말한다    [코드]import java.io.*;import java.util.*;public class.. 2024. 5. 3.
[백준] 1120번 문자열 JAVA (자바) 풀이 문제 1120 (문자열, 브루트포스) 길이가 N으로 같은 문자열 X와 Y X와 Y의 차이 = X [i] ≠ Y [i]인 i의 개수 (예, X = ”jimin”, Y = ”minji” 이면, 차이 = 4) 짧은 문자열 앞 혹은 뒤에 아무 알파벳 추가 연산을 반복해 문자열 길이를 같게 만든다 이때, 문자열 길이가 같으면서, 차이를 최소로 하는 프로그램을 작성해라 [입력] : 첫째 줄에 A, B 길이 ( 최대 50 / A 길이 ≤ B 길이 / 소문자 ) [출력] : 최소의 차이 출력 [참고] 규칙찾기 문자열 길이 차이 구하기 A문자열에 몇개의 알파벳을 더 붙여야 하는지 알기 위해서 문자열 길이 차이 = A 문자열 길이 만큼 다 순회하고 남은 개수 예를 들어 A = abc, B = eabcd 라면 처음엔 A의 .. 2024. 4. 16.
[백준] 1057번 토너먼트 JAVA (자바) 풀이 문제 1057 (수학, 브루트포스) 토너먼트 과정 1번부터 N번의 선수 중 서로 인접한 번호끼리 스타를 한다 이긴 사람은 다음 라운드에 진출하고 최후의 한 명이 남을 때까지 진행 라운드의 참가자가 홀수명일 경우, 마지막 번호는 다음 라운드로 자동 진출 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다 (처음 정해진 순서 유지하면서) 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정 김지민과 임한수가 몇 라운드에서 대결하는지 출력해라 [입력] : 첫째 줄에 참가자 수 N, 김지민과 임한수의 번호 입력 ( 2 ≤ N ≤ 100,000 자연수 ) [출력] : 김지민과 임한수가 대결하는 라운드 번호 출력 (서로 대결하지 않을 때, -1을 출력) [참고] 규칙찾기 홀수일 경우 다음 라운드 순번 N/2.. 2024. 4. 16.
[백준] 2003번 수들의 합2 JAVA (자바) 풀이 문제 2003 N개의 수로 된 수열 = A[1], A[2], …, A[N] 수열의 i ~ j번째 수까지의 합 = A[i]+ … + A[j] = M이 되는 경우의 수 [입력] : 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) : 다음 줄에는 A[1], A[2], …, A[N] (공백으로 분리 & 각각의 A[x]는 30,000을 넘지 않는 자연수) [출력] : 경우의 수 출력 [참고] 기준숫자를 하나 잡고 합이 M될 때까지 for문 돌리기 check(j) = 시작 숫자 일단 j를 입력받으면 바로 이전 숫자들과 합부터 계산 수열 합이 M이 되면 count하고 for문 break 수열 합이 M을 넘어서면 바로 for문 break [코드] import java.io.*; i.. 2024. 4. 11.
[백준] 1018번 체스판 다시 칠하기 JAVA (자바) 풀이 문제 1018 M x N 크기 보드 (검정색 & 흰색) 보드를 잘라서 8 x 8 크기의 체스판으로 만들기 체스판 규칙 : 검적생 흰색 번갈아서 칠할 것 잘라낸 보드 판을 체스판 규칙에 맞게 다시 칠해야 하는 최소 횟수를 구하시오 [입력] : 첫째 줄에 N과 M ( 8보다 크거나 같고 50보다 작거나 같은 자연수) : 둘째 줄부터 N개의 줄 보드 각 행의 색이 주어진다 ( B = 검은색, W = 흰색 ) [출력] : 다시 칠해야 하는정사각형 개수 [참고] 1. 맨 처음 시작 판을 기준으로 번갈아 색을 칠할 것! 첫 시작판을 한가지 색으로 고정하자! 흰색판일 경우로만 진행하는 것 흑과 백 경우의 수가 2개 이므로 boolean을 사용! (0과 1로 사용해도 괜찮다) 반대색은 무조건 64 - (count) 위.. 2024. 4. 11.
[백준] 1065번 한수 JAVA (자바) 풀이 문제 1065 한수 = 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다 등차수열 = 연속된 두 개의 수의 차이가 일정한 수열 예) [ 1, 1, 1 ] , [ 1, 2, 3 ] , [ 1, 3, 5 ], 등 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력 [입력] : 첫 번째 줄 1,000보다 작거나 같은 자연수 N [출력] : 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력 [참고] 1. 일의 자리 숫자 / 십의 자리 숫자는 무조건 한수이다 (1~99까지는 한수 99개) 1의 자리 숫자 자릿수가 1개 뿐이라 비교될 숫자가 없어서 그 자체로 수열 ex) 1 ▶ 즉 한수이다 ( 공차 없음 ) 10의 자리 숫자 자릿수가 2개 뿐이라 어차피 비교 대상은 하나이기 때문에 일정한 공차를.. 2024. 4. 10.

티스토리툴바