티스토리 뷰
728x90
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
- 문제 :
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
- 풀이 :
완전탐색으로 해결한 문제였습니다.
풀이입니다.
1. 모든 좌표,( 0 ~ N)에 대해 k=1부터 N+1까지 범위를 늘려가며 확인한다.
2. 이 때, 해당 범위에 있는 집의 개수와 기업이 이득을 보는지 손해를 보는지 확인한다.
3. 만약, 현재까지 탐색한 집의 개수 중 MAX값보다 현재 탐색한 집의 개수가 많다면 정답을 갱신한다.
- 소스코드 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Solution {
static int TC, N, M, answer, hCount;
static int[] price;
static ArrayList<int[]> house;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
TC = Integer.parseInt(br.readLine());
price = new int[22];
for (int i = 0; i < 22; i++) {
price[i] = i * i + (i-1) * (i-1);
}
for (int testCase = 1; testCase <= TC; testCase++) {
sb.append("#").append(testCase).append(" ");
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
answer = 0;
house = new ArrayList<int[]>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
if (st.nextToken().equals("1"))house.add(new int[] {i,j});
}
}
for (int k = 1; k <= N+1; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
hCount = 0;
for (int[] h : house) {
if(distance(h, i, j) < k) {
hCount ++;
}
}
if (hCount > answer && hCount*M- price[k] >= 0) {
answer = hCount;
}
}
}
}
sb.append(answer).append("\n");
}
System.out.println(sb.toString());
}
private static int distance(int[] h, int i, int j) {
return Math.abs(h[0] - i) + Math.abs(h[1] - j);
}
}
320x100
'Algorithm > Brute Force' 카테고리의 다른 글
(Java/자바) - 백준(BOJ) 2615번 : 오목 (0) | 2022.07.23 |
---|---|
(Python/파이썬) - 백준(BOJ) 1051번 : 숫자 정사각형 (1) | 2022.07.06 |
(Python/파이썬) - 백준(BOJ) 25047번 : 사각형 게임 (Large) (0) | 2022.05.13 |
(Python/파이썬) - 백준(BOJ) 25046번 : 사각형 게임 (Small) (0) | 2022.05.13 |
(Python/파이썬) - 백준(BOJ) 15683번 : 감시 (0) | 2022.05.11 |
댓글
© 2022 WonSeok, All rights reserved