본문 바로가기

컴퓨터 공학/백준75

[백준] JAVA 자바 : 1, 2, 3 더하기 (9095번) 사실 아직까지 DP 알고리즘 문제들은 대개 비슷한 유형이라서… 그냥 dp[] 배열에 이전 값들의 경우의 수를 저장해둔 다음 바텀탑이나 탑다운 방식으로 dp[] 배열을 완성해 나가면 된다. 나 같은 경우는 바텀탑이 편해서 바텀탑만 사용하는 중… 이 문제 같은 경우도 똑같이 해결할 수 있다! 그러나 최대 3까지 더할 수 있으므로 나는 초깃값을 3개 설정해 두고, for 반복문을 4부터 n까지 돌리게 작성했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Sum123 { public static int stoi(String str) { return Integer.pa.. 2024. 1. 22.
[백준] JAVA 자바 : 2×n 타일링 2 (11726번) 직전 문제인 2×n 타일링에서 추가할 수 있는 블럭의 개수가 하나 늘어난 케이스이다. 이건 2×n 타일링 문제를 이해하고 푸셨다면… 진짜 2분 안에 해결하실 수 있을 것 같다. 기존의 dp[i] = dp[i-1] + dp[i-2]라는 코드는 dp[i]에 1×2로 채우는 경우 + 2×1로 채우는 경우를 뜻했다. 그러나 2×1로 채우는 경우의 수는 2×2로 채우는 경우의 수와 똑같으므로… dp[i-2]를 더해줄 때 2배를 해서 더해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Tiling_2n_2 { public static int stoi(String .. 2024. 1. 22.
[백준] JAVA 자바 : 2×n 타일링 (11726번) 사실 이 문제 이전에 나온 1로 만들기 문제는 못 풀어서 구글링해서 겨우 풀었는데…ㅋㅋ DP 알고리즘을 한 번 이해하고 나니까 이런 문제 정도는 굉장히 쉽게 풀리는 듯? 아직 실버3 수준이라서 그런지… 조금만 사고하면 어렵지 않게 풀 수 있다. DP알고리즘의 여느 때처럼 이전 값들을 저장할 수 있는 배열을 만들어준 다음 0번째 인덱스와 1번째 인덱스에 1을 할당한다. (초깃값 설정) 이후 Bottom-Top 방식을 채용해서 i를 2부터 X까지 반복시키면서 dp[i]에는 dp[i-1] + dp[i-2], 즉 1×2로 채우는 방식 + 2×1로 채우는 방식의 경우의 수를 더해주면 된다. import java.io.BufferedReader; import java.io.IOException; import jav.. 2024. 1. 22.
[백준] JAVA 자바 : Base Conversion (11576번) 문제를 읽어보면 이해하기 굉장히 어렵지만 단순하게 설명하면 A진법으로 표현된 수를 B진법으로 변환하는 문제이다. 백준 문제를 풀다보면 항상 문제를 이해하기 어렵게 설명해 놓는다… 해외 문제들을 번역해서 가져오는 경우가 많아서 그런가? 나도 나름 책도 열심히 읽는데… 문제만 보고는 이해가 안 돼서 구글링해서 문제 뜻을 이해하는 경우가 종종 발생한다…ㅋㅋㅋㅋ 여하튼 이 문제는 A진법의 수를 10진법으로 변환한 후 그 10진수를 B진법 수로 바꿔서 출력하면 해결할 수 있다. 사실 이 문제 굉장히 많이 틀렸는데… 4번을 틀리고 5번째서야 비로소 맞췄다. 그런데 나는 틀린 이유가 오버플로우를 처리 못 해서 계속 틀린 줄 알고 오버플로우를 어떻게 처리할지만 계속 고민했는데… 알고보니 0을 넣었을 때를 처리 안 해줘.. 2024. 1. 22.
[백준] JAVA 자바 : 소인수분해 (11653번) 소인수 분해하는 문제이다. 소수 판정만 한다면 쉽게 풀 수 있을 것이다. 나같은 경우는 2부터 돌면서 소수인 수에 한해서 그 수로 나눠진다면 StringBuilder에 그 수를 담은 후 마지막에 출력했다. 근데 이렇게 돌리니까 180ms가 나오는데… 순위권에 계신 분들은 보면 70~80ms 언저리시다… 보면서 공부 좀 해야겠네… import java.io.*; import java.util.Arrays; public class Factorization_11653 { public static int stoi(String str) { return Integer.parseInt(str); } public static void main(String[] args) throws IOException { Buffer.. 2024. 1. 22.
[백준] JAVA 자바 : 진법 변환 (2745번) 앞에서 봤던 진법 변환 2가 10진수에서 B진수로 바꾸는 문제였다면, 이 문제는 B진수를 10진수로 바꾸는 문제이다. 사실 진법 변환을 잘 몰랐는데 이번에 문제들을 풀면서 잘 배워간다(…) 자릿수 별로 B의 자릿수 제곱을 곱한 값들을 다 더해주면 된다! 브론즈라 그런지 크게 어려운 부분은 없는 문제. import java.io.*; import java.util.StringTokenizer; public class RadixChange_2745 { public static int stoi(String str) { return Integer.parseInt(str); } public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 1. 22.
반응형

티스토리툴바