0과 1의 쉼터

문제https://www.acmicpc.net/problem/4150 풀이주어진 N에 대한 피보나치 수를 구하는 문제다.정답은 최대 1000자를 넘을 수 있기 때문에 기본 자료형으로는 문제를 풀 수 없다.BigInteger을 사용해 해결하면 된다. List f = new ArrayList(); // Solve f.add(BigInteger.valueOf(0)); f.add(BigInteger.valueOf(1)); f.add(BigInteger.valueOf(1)); for (int i = 3; i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online..

문제https://www.acmicpc.net/problem/13419 풀이주어진 문자열에 대해 두 명이 탕수육 게임을 한다고 한다.자신의 차례 때 말해야 하는 문자로만 이루어진 최소 문자열을 출력하는 문제다.자신의 순서(0 또는 1번 인덱스)에서 2개씩 건너뛰며 다시 자신의 순서로 돌아올 때 까지 문자를 선택하면 된다. int idx = 0; StringBuilder a = new StringBuilder(); StringBuilder b = new StringBuilder(); do { a.append(S.charAt(idx)); idx = (idx + 2) % S.le..

문제https://www.acmicpc.net/problem/14656 풀이입력받은 N명의 학생 중 순서대로 서있지 않은 학생의 수를 구하는 문제다.인덱스는 0부터 시작이니, i번째 학생의 번호가 i + 1와 일치하지 않는 경우를 세면 된다. // Solve int cnt = 0; for (int i = 0; i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/14656.java

문제https://www.acmicpc.net/problem/1354 풀이주어지는 N에 대해 $A_N$을 구하는 문제다.단 N은 최대 $10^{13}$이며, 중복되는 계산을 최소화 해야한다.범위가 넓기 때문에 Map을 사용해서 중간 계산을 기록하면 된다. private static long getA(long i) { if (i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01354.java

문제https://www.acmicpc.net/problem/1052 풀이N개의 병을 2개씩 합쳐서 하나의 병으로 만드는 문제다.만약 K개의 병으로 만들 수 없다면 병을 한 개 더 추가해 다시 합칠 수 있다.2개의 병을 한 개의 병으로 합치기 때문에 N을 최대로 합칠 수 있는 병의 수는 N을 이진수로 했을 때 1의 개수와 동일하다.예제 1번은 다음과 같다.1 1 1 1 1 1 1 1 1 1 1 1 12 2 2 2 2 2 14 4 4 18 4 1$13=1101_{(2)}$으로 필요한 병의 수는 3개지만, K는 2이므로 병을 더 추가해야 한다.$14 = 1110_{(2)}$에 대해 K는 2, 추가된 병은 1개다. 14개의 병을 합쳐 총 3개의 병에 { 8, 4, 2 }담을 수 있다.이를 코드로 구현하면 다음..

문제https://www.acmicpc.net/problem/10698풀이입력받은 수식이 올바른지 판단하는 문제다.소스코드보기

문제https://www.acmicpc.net/problem/19621 풀이N개의 회의실 정보와, 회의 참여 인원이 시간 순서대로 주어졌을 때회의를 진행할 수 있는 최대 인원을 구하는 문제다.문제에서는 K번째 회의는 K - 1, K + 1번째 회의와 시간이 겹치지만, 다른 회의와는 시간이 겹치지 않는다고 명시되어있다.dp로 쉽게 풀이할 수 있다.dp[i] : i 번째 회의까지 참석 가능한 최대 인원 수dp[i - 2]에 현재 회의를 진행하는 것과, dp[i - 1]을 그대로 진행하는 것 중 선택하면 된다.따라서 점화식은 다음과 같다.dp[i] = max(dp[i - 1], dp[i - 2] + 1) dp[1] = A[1]; for (int i = 2; i 소스코드https://g..

문제https://www.acmicpc.net/problem/30389 풀이주어지는 N개의 문자열에 대해 모든 부분 접미사 집합을 구하고, 다음 문자열의 접미사 집합과 XOR연산을 하는 문제다.우선 현재 문자열의 접미사를 구해주는 메서드를 만들자.입력받은 문자열을 역순으로 한 칸씩 늘려가며 문자열을 결합해서 저장하면 된다. private static List getSuffixes(String s) { StringBuilder sb = new StringBuilder(); List suffixes = new ArrayList(); for (int i = s.length() -1; i >= 0; --i) { sb.append(s.charAt(i)..

문제https://www.acmicpc.net/problem/1025 풀이N*M 의 보드에서 행과 열이 등차수열을 이루는 칸들의 숫자를 이어 붙여 만든 수가, 어떤 정수의 제곱수 중 가장 큰 제곱수를 찾는 문제다.만약 찾지 못했다면 -1을 반환해야 한다. int res = -1; for (int i = 0; i 행과 열에 대한 등차수열이기 때문에 각 위치에 2N * 2M 범위에 대한 등차수열을 찾으면 된다. for (int dx = -N; dx 만약 증가값이 둘 다 0이라면 탐색이 불가능하므로 유의하며, 숫자를 이어 붙인 후 가장 큰 제곱수를 찾아주면 된다. if (dx != 0 || dy != 0) { ..

문제https://www.acmicpc.net/problem/1013 풀이입력으로 주어지는 여러 문자열들이 지문에서 주어진 패턴과 동일한 문자열인지 판별하는 문제다.정규표현식을 사용해 쉽게 풀이할 수 있다. Pattern pattern = Pattern.compile("^(100+1+|01)+$"); while (T-- > 0) { // Solve sb.append(pattern.matcher(br.readLine()).matches() ? "YES\\n" : "NO\\n"); }소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/nor..