지구정복

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net -문제해설 기본적인 다이나믹 프로그래밍 문제이다. 바텀업방식으로 풀면 금방 풀 수 있다. 이때 dp 배열은 long타입으로 선언해야된다. 점화식은 다음과 같다. dp[n] = dp[n-3] + dp[n-2] (단, n이 1 또는 2일 때는 dp[1] = 1, dp[2] = 1 ) -자바 package ex; import java.io.BufferedReader; import java.io.IOExcep..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net -문제해설 옷의 종류만 중요하고 옷이 무엇인지는 중요하지 않다. HashMap을 이용해서 동일한 옷의 종류면 그냥 옷의 개수를 1씩 올리고 없으면 새로운 옷의 종류를 키로 삽입하고 값은 1로 설정한다. 그리고 아래 공식으로 출력값을 만든다. sum = (첫 번째 종류의 옷 개수 + 1) * (두 번째 종류..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net -문제해설 풀다가 어려워서 이 분의 코드를 참고했다. https://st-lab.tistory.com/227 먼저 문제와 나와있는 대로 정사각형에 모든 값이 1이 아니거나 0이 아니면 현재 정사각형을 2등분해서 각 사분면에 대해서 다시 전체 값이 1인지 0인지를 검사한다. 이때 전체값이 1이거나 0이면 재귀함수를 빠져나오고 아닐 경우 재귀함수를 계속 호출한다. 아직 분할..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net -문제해설 먼저 입력 좌표값들을 배열에 저장하고 이 배열을 복사한다. 복사된 배열을 오름차순으로 정렬한다. 그리고 정렬된 배열을 순회하면서 해시맵에 넣어준다. 이때 키는 정렬된 배열의 값이 들어가고 값으로는 좌표압축값인 idx가 들어간다. 또한 무작정 집어넣는 것이 아니라 해시맵에 똑같은 키가 있을 경우엔 건너뛰게 된다. -자바 package so..