https://www.acmicpc.net/problem/28217 28217번: 두 정삼각형 첫 번째 줄에는 $1$개의 수를, 두 번째 줄에는 $2$개의 수를, $\dots$, $N$번째 줄에는 $N$개의 수를 아래 그림과 같이 배치한 정삼각형 $A$, $B$가 주어진다. 각 위치에 있는 수는 $0$ 또는 $1$이다. 당신은 www.acmicpc.net 풀이 더보기 삼각형 A와 B를 비교해서 2개가 다르면 다른거 갯수를 전부 계산한 것 중 가장 작은 수를 표기 입력 첫번째 줄 N: 정삼각형 크기 N개 줄 A의 수 N개 줄 B의 수 가장 간단하게 하는 것은 A가 나올 수 있는 경우의 수를 모두 구한 후 전부 B랑 비교하면 해결된다. 1. 입력 정삼각형 2. A를 시계방향 rotate 1번 (120도) 3..
Algorithms
https://www.acmicpc.net/problem/5549 5549번: 행성 탐사 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 www.acmicpc.net 풀이 더보기 행성은 정글, 바다, 얼음이 뒤얽힌 행성 가로 N, 세로 M 정글: J, 바다: O, 얼음: I 조사대상 영역 K개 이 영역에 정글, 바다, 얼음이 몇개씩 있는지 구해야 함 입력 첫째 줄 M, N 둘째 줄 K M개 줄 상근이가 보낸 지도 내용 K줄 조사 대상 영역의 정보 a, b, c, d 왼위, 오아 좌표 출력 각 조사 대상 영역에 포함된 정글, 바다, 얼음의 수를 공백으로 구분해 표..
https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 더보기 로봇의 지형은 N*M 왼쪽, 오른쪽, 아래로만 이동 가능 한번 탐색한 지형은 탐사 불가 1,1 -> N, M 이동 첫째 줄 N, M N개의 줄에 M개의 수 배열 최대 가치 출력 맵에서 현재 위치(i, j) -> 이전 위치(i, j-1), (i, j+1), (i-1,j) 좌위에서 한번, 우위에서 한번 계산해서 둘 중 더 큰 수를 대입 첫째줄 dp 0 1 2 3 4 0 10 10..
https://www.acmicpc.net/problem/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 더보기 첫째 줄 N: 투자 금액 M: 투자 가능한 기업들의 갯수 N개의 줄 번호 투자액 기업이익 4 2 1 5 1 2 6 5 3 7 9 4 10 15 투자금액/기업 1 2 1 5 1 2 6 5 3 7 9 4 10 15 dp[i][j]: 1~j번째 기업까지 i원 사용했을 경우 최대 이익 구하고자 하는 값\ dp[N][M]은 최대값 path[N][M]은 M기업에 얼마나 투자했는가가 저장되어 있음 dp 표..
https://www.acmicpc.net/problem/3691 3691번: 컴퓨터 조립 각 테스트 케이스에 대해서, 상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터의 성능을 출력한다. www.acmicpc.net 풀이 더보기 첫째 줄 테스트 케이스: 100개를 넘지 않음 첫째 줄 부품의 갯수: n 예산 b n개의 줄 부품의 정보 type: 부품의 종류, name: 부품의 이름, price: 가격, quality: 성능 상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터 성능 hashmap에 저장 list 구성 순서대로 가격과 성능을 정렬한 순서대로 정렬 각각의 가격 성능 list를 가격이 낮은 순으로 오름차순 정렬 일단 전부 가장 낮은걸로 부품들을 넣는다. 이후 성능 낮은 부품을 꺼내서 해당 부품..
https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 더보기 ccw 로 삼각형 구해서 다 더하면 된다. 코드 package test2166; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.OutputStreamWriter;..
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 풀이 더보기 벡터의 외적을 이용하여 구하는 방식이다. 점 3개가 주어졌을 때 벡터의 외적을 구해서 외적 값이 0보다 크면 반시계 0이면 일직선 0보다 작으면 시계 방향으로 계산한다. x1 x2 x3 \ \ y1 y2 y3 x1 x2 x3 / / y1 y2 y3 즉 (x1*y2 + x2*y3 + x3*y1) - (x2y1 + x3y..
이진 탐색 트리 다국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (하단 참고) 128 MB 6881 1113 790 24.976% 문제 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다. 1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만들려고 한다. 이제 배열의 첫 번째 수를 루트 노드로 놓고, 다른 나머지 수들을 순서대로 삽입하면서 이진 탐색 트리를 만들려고 한다. 즉, 첫 번째 수를 제외한 모..
숫자구슬 스페셜 저지 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 6966 1770 1185 26.755% 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0..
정점들의 거리 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 11899 4761 3110 38.338% 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 입력된다. 두 점 사이의 거리는 10,000보다 작거나 같은 자연수이다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 예제 입력 1 복사 7..
