자바
백준 JAVA 11726번 2xn 타일
백준 JAVA 11726번 2xn 타일
2021.12.29문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ▶ 문제 2xn 직사각형안에 1x2와 2x1 타일을 채운다. ▶ 해설 DP 문제로 판단되어 점화식을 세웠다. 2 = 2 3 = 3 4 = 5 5 = 8 .... 9 = 55 위 처럼 나오므로 점화식은 DP[N]=DP[N-1]+DP[N-2]로 도출 할 수 있었다. import java.io.*; public class Main { public static void main(String[] args) thro..
백준 JAVA 17609번 회문
백준 JAVA 17609번 회문
2021.12.24문제 링크: https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제를 접할 때 회문이 아닐 경우에 for문을 중첩해서 한 글자씩 빼낸 후 확인을 했을 경우 시간초과가 나왔다. (해당 코드 첨부) import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int t; static boolean check; public static void main(String [] ar..
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
백준 JAVA 11722번 가장 긴 감소하는 부분 수열
2021.12.23문제 링크: https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 해당 문제를 처음에는 DFS로 시도했지만 시간초과로 실패했다. 그래서 DP로 다시 풀어 보았다. import java.math.BigInteger; import java.util.*; import java.io.*; public class Main { static int [] arr; static int t; ..
백준 JAVA 2252번 줄세우기
백준 JAVA 2252번 줄세우기
2021.12.18문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 키를 정렬하는데 있어서 약간의 순서를 줬다. 즉 어떤 학생 앞에는 정해진 학생이 앞에 있어야 하는 것이다. arr배열에 조건의 수를 적어주고 list[해당 학생].add(앞에 서야하는 학생)식으로 선언해준다. arr[학생]==0 일 경우에 StringBuilder에 추가해주며 해당 학생 앞에 서야하는 학생의 arr을 낮춰준다. 이때 낮춰준 학..
백준 JAVA 19532번 수학은 비대면 강의입니다.
백준 JAVA 19532번 수학은 비대면 강의입니다.
2021.12.10문제 링크: https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 단순한 브루트 포스 문제이다. ax+by=c 와 dx+ey=f를 만족하는 x,y를 반복문을 통해서 모든 경우의 수를 탐색해주면 된다. import java.util.*; import java.io.*; public class Main { public static void main(..
백준 JAVA 14891번 톱니바퀴
백준 JAVA 14891번 톱니바퀴
2021.12.04문제 링크: https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 문제로서 하나의 톱니바퀴를 돌렸을 때 옆에 있는 톱니바퀴들이 돌아간다면 상태 배열을 변경시키고 상태 배열에 따라서 시계방향, 반시계방향으로 돌려주면된다. 시작 지점에서의 시계, 반시계 방향으로 퍼져나가는 것을 생각해주면 어려운 문제는 아니다. import java.util.*; import java.io.*; class info{ int num; int dir; publ..