본문 바로가기

Java123

[백준] 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.
[백준] 15661번 링크와 스타트 JAVA (자바) 풀이 문제 15661 (비트마스킹) : 축구는 평일 오후에 하고 의무 참석도 아니다. : 축구를 하기 위해 모인 사람은 총 N명, 이제 스타트 팀과 링크 팀으로 사람들을 나눈다. (한 명 이상) : 번호를 1부터 N까지로 배정했고 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. (예시) N=4이고, S가 아래와 같은 경우를 살펴보자. 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다. 스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력.. 2024. 2. 26.
[백준] 2343번 기타 레슨 JAVA (자바) 풀이 문제 2531번 (이분탐색) : 블루레이에는 총 N개의 강의가 들어가는데, : 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. : M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다 (강의의 길이가 분 단위) 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. ( 단, M개의 블루레이는 모두 같은 크기 ) [입력] : 첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 블루레이 수 M (1 ≤ M ≤ N) : 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위 (각 강의의 길이는 10,000분을 넘지 않는다) [출력] : 가능한 블루레이 크기중.. 2024. 2. 26.
[백준] 20310번 타노스 JAVA (자바) 풀이 문제 20310 0과 1로 이루어진 문자열 S S가 포함하는 0의 개수와 1의 개수는 모두 짝수 갑자기 타노스는 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 S'를 만들고자 한다 S'로 가능한 문자열 중 사전순으로 가장 빠른 것을 구해라 [입력] : 문자열 S [출력] : 문자열 중 사전순으로 가장 빠른 것을 출력 [코드] import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(.. 2024. 1. 30.
[백준] 17484번 진우의 달 여행 JAVA (자바) 풀이 문제 17484 지구와 우주사이는 N X M 행렬 각 원소의 값 = 지날 때 소모되는 연료 양 연지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 연료의 최소값을 구해라 지구 → 달 경우 우주선 이동 가능 방향 우주선 이전에 움직인 방향으로 움직일 수 없다 (같은 방향으로 두번 연속 이동 불가) [입력] : 첫 번째 줄 지구와 달 사이 공간을 나타내는 행렬 크기 N, M ( 2≤ N, M ≤ 6 ) : N줄 동안 각 행렬의 원소 값 ( 행렬의 원소값은 100 이하의 자연수 ) 6 4 5 8 5 1 3 5 8 4 9 77 65 5 2 1 5 2 5 98 1 5 4 95 67 58 [출력] : 최소 연료의 값 29 [코드] import java.io.*; import java.util.*; class .. 2024. 1. 30.

티스토리툴바