본문 바로가기

자바146

[SWEA] 1491. 원재의 벽 꾸미기 D3 JAVA (자바) 풀이 문제 1491번 (브루트포스) 1 X 1타일 N개를 이용해 R X C 크기의 직사각형 인테리어 만들기원재의 방은 정사각형 형태이기 때문에 만드는 직사각형 인테리어를 최대한 정사각형에 가깝게 만들면서 최대한 많은 타일을 사용해라가중치 A, B를 가지고 나름의 식 = A X lR – Cl + B X (N - R X C)위의 값을 최소화하라 [입력] 첫 번째 줄에 테스트 케이스의 수 T 각 테스트 케이스의 첫 번째 줄에는 세 정수 N, A, B(1 ≤ N, A, B ≤ 105) [출력] 각 테스트 케이스마다 ‘#x'를 출력하고, 답을 출력한다.    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  ※ 최적의 조건 ※  A X |R – C| + B X (N - R X C) A, B, .. 2024. 5. 12.
[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View D3 JAVA (자바) 풀이 문제 1206번 (브루트포스) 왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다조망권이 확보된 세대의 수를 반환해라 [EX]  연두색으로 색칠된 6세대는 2칸 이상의 공백이 존재하므로 조망권 확보A와 B는 왼쪽 조망은 2칸 이상 확보, 오른쪽 조망은 한 칸만 확보C의 경우는 오른쪽 조망은 2칸이 확보, 왼쪽 조망이 한 칸 확보 [제약 사항] 가로 길이는 항상 1000이하맨 왼쪽과 맨 오른쪽 두 칸 공백각 빌딩의 높이는 최대 255   [입력]: 10개의 테스트케이스: 각 테스트케이스의 첫 번째 줄에는 건물의 개수 N (4 ≤ N ≤ 1000)  그 다음 줄에는 N개의 건물의 높이 (0 ≤ 각 건물의 높이 ≤ 255)  (맨 왼쪽, 오른쪽 두 칸에 있는 건.. 2024. 5. 12.
[백준] 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.
[SWEA] 3307. 최장 증가 부분 수열 D3 JAVA (자바) 풀이 문제 3307. 최장 증가 부분 수열 (DP) 수열 : { A1, A2, ... , AN }최장 증가 부분 수열 : { B1, B2, ... , BK }  (0≤K≤N, B1 AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.[입력]: 첫 번째 줄 테스트 케이스의 수 T: 각 테스트 케이스의 첫째 줄에 수열의 길이 N(1≤N≤1,000)  둘째 줄에는 수열의 원소 N개 ( 1 ≤ N  ≤ 2³¹-1 자연수)[출력] ‘#T’ 최대 증가 부분 수열의 길이 출력   [과정] 초기 방식) 시작점을 하나씩 고정하면서 다음 노드로 순차적으로 돌면서 수가 더 크면 길이를 count 하는 방식으.. 2024. 5. 7.
[백준] 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.

티스토리툴바