우 -> 하 -> 좌 -> 상 순서로 계속 움직일 것이므로 미리 순서에 맞게 dx, dy 배열을 저장.
처음 좌표는 (0,0) 방향은 dir=0 (우 방향)
i부터 N*N까지 순차적으로 저장해준다.
범위를 벗어나거나 이동할 곳에 값이 이미 있는 경우마다 방향을 회전해준다.
좌표를 다시 원래대로 돌려준 후에
방향 전환하고
다시 전환한 방향으로 이동
import java.io.*;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
for(int tc=1; tc<=T; tc++) {
int N = Integer.parseInt(br.readLine());
//N 이 1인 경우를 따로 처리
if(N == 1) {
System.out.println("#"+tc);
System.out.println(1);
continue;
}
int[][] arr = new int[N][N];
int x = 0;
int y = 0;
int dir = 0; //처음 방향은 0(우 방향)
for(int i=0; i<N*N; i++) {
arr[x][y] = i+1;
x += dx[dir];
y += dy[dir];
//범위를 벗어나는 경우 방향 전환
if(x >= N || y >= N || x < 0 || y < 0) {
//원래 위치로 돌려주고
x -= dx[dir];
y -= dy[dir];
//방향 전환 (0->1 우에서 하/ 1->2 하에서 좌/ 2->3 좌에서 상/ 3->0 상에서 우)
dir = (dir+1)%4;
//전환한 방향으로 이동
x += dx[dir];
y += dy[dir];
}
//이동할 곳에 값이 있는 경우 방향 전환
if(arr[x][y] != 0) {
x -= dx[dir];
y -= dy[dir];
dir = (dir+1)%4;
x += dx[dir];
y += dy[dir];
}
}
System.out.println("#"+tc);
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
}
}
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1;tc<=T;tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] a = new int[N];
int[] b = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
b[j] = Integer.parseInt(st.nextToken());
}
int max = 0;
int tmp = 0;
if(N < M) {
for(int j=0; j<=M-N; j++) { //인덱스가 M-N을 넘어가면 비교할 범위(N개)가 넘어가므로
int k=j; //비교할 위치
int sum = 0;
for(int i=0; i<N; i++) { //N개만큼동안 a배열과 b배열의 값을 곱해준다.
tmp = a[i] * b[k++]; //a배열값과 b배열값 곱해주기
sum += tmp; //곱한 값을 계속 더해준다.
}
if(sum > max) max = sum; //최댓값을 저장
}
} else if(N == M) { //크기가 같은 경우에 최댓값의 경우는 한가지.
for(int i=0; i<N; i++) {
max += a[i]*b[i];
}
} else { // N이 더 큰 경우. M이 더 큰 경우와 반대로 해주면 된다.
for(int j=0; j<=N-M; j++) {
int k=j;
int sum = 0;
for(int i=0; i<M; i++) {
tmp = a[k++] * b[i];
sum += tmp;
}
if(sum > max) max = sum;
}
}
System.out.println("#"+tc+" "+max);
}
}
}
먼저 사용자들의 이동 정보를 각 배열에 저장하고 BC의 정보는 AP클래스를 만들어서 ArrayList에 저장하였다.
시간에 따라 이동하면서 각 시간마다 A와 B의 충전량 합의 최댓값을 구해준다.
최댓값은 사용자가 각각 사용할 수 있는 충전량을 배열에 저장해놓고 모든 경우를 구해줬다.
이때 i == j 인 상황이 됐을 때 한쪽은 0 (해당 BC를 사용할 수 없는 경우)일 수도 있으므로 무조건 반으로 나눠주면 안 되고 둘 다 해당 BC를 이용하고 있는지 확인해주어야 한다. (같은 p값을 가지는지 확인)
시간마다의 최댓값을 모두 더해준 후에 출력
import java.io.*;
import java.util.*;
public class Solution {
static class AP {
int x;
int y;
int c;
int p;
AP(int x, int y, int c, int p) {
this.x = x;
this.y = y;
this.c = c;
this.p = p;
}
}
static int M,A;
static int dx[] = {0,-1,0,1,0};
static int dy[] = {0,0,1,0,-1};
static int Ainfo[];
static int Binfo[];
static ArrayList aplist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
A = Integer.parseInt(st.nextToken());
Ainfo = new int[M];
Binfo = new int[M];
//사용자 A의 이동정보
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++) {
Ainfo[i] = Integer.parseInt(st.nextToken());
}
//사용자 B의 이동정보
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++) {
Binfo[i] = Integer.parseInt(st.nextToken());
}
//BC의 정보를 ArrayList에 저장한다.
aplist = new ArrayList();
for(int i=0; i<A; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
aplist.add(new AP(x,y,c,p));
}
int ans = move();
System.out.println("#"+tc+" "+ans);
}
}
static int move() {
int x1 = 1;
int y1 = 1;
int x2 = 10;
int y2 = 10;
//0초일때의 합
int sum = getMax(x1,y1,x2,y2);
//시간별로 이동하면서 그때마다의 최대값을 합해준다.
for(int time=0; time<M; time++) {
x1 += dx[Ainfo[time]];
y1 += dy[Ainfo[time]];
x2 += dx[Binfo[time]];
y2 += dy[Binfo[time]];
sum += getMax(x1,y1,x2,y2);
}
return sum;
}
static int getMax(int x1, int y1, int x2, int y2) {
int[][] amount = new int[2][A];
//2차원 배열에 사용자A(0)와 사용자B(1)의 BC별로 충전가능한 값을 저장해준다.
//사용자A의 충전 가능한 BC의 p값
for(int j=0; j<A; j++) {
amount[0][j] = check(x1,y1,j);
}
//사용자B의 충전 가능한 BC의 p값
for(int j=0; j<A; j++) {
amount[1][j] = check(x2,y2,j);
}
//사용자 A와 사용자 B의 충전량의 합중 최댓값을 구해준다.
int max = 0;
for(int i=0; i<A; i++) {
for(int j=0; j<A; j++) {
int sum = amount[0][i]+amount[1][j];
// 같은 BC를 이용하는 경우 값을 반으로 나눠줘야한다.
// 주의할 점은 한 쪽은 아예 값이 0일수도 있으므로(해당 BC를 이용할 수 없는 위치) 정확히 둘다 같이 이용하고 있는 경우에만 나누어주어야한다.
if(i == j && amount[0][i] == amount[1][j])
sum /= 2;
if(sum > max) max = sum;
}
}
return max;
}
static int check(int x, int y, int apnum) {
int a = Math.abs(x-aplist.get(apnum).x);
int b = Math.abs(y-aplist.get(apnum).y);
int dist = a+b;
//해당 BC에 포함되는 경우에 p값을 리턴
if(dist <= aplist.get(apnum).c)
return aplist.get(apnum).p;
else
return 0;
}
}
이번에는 두 가지 방법으로 풀어보았다. 사실 첫 번째 풀이(BFS)로 풀고 다른 사람들 실행 시간과 비교해봤을때 엄청 빠르게 푼 사람이 있어서 다른 사람들 풀이 좀 찾아보고 다시 풀어봤다ㅠㅠ 두 번째 풀이가 훨씬 빠를 뿐만아니라 메모리 차이도 엄청나다...
두 번째 풀이첫 번째 풀이
첫 번째 풀이 (BFS 풀이)
K 값이 커질 때마다 BFS가 단계별로 진행하는 모양과 같기 때문에 BFS로 풀었다.
N의 범위가 (5 ≤ N ≤ 20) 이므로 완전 탐색을 해줬다.
모든 칸에 대해서 bfs를 통해 서비스 영역 모양 처럼 퍼지도록 계산해줬다.
K 값이 증가할때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
K 값이 바뀌는 것은 큐 사이즈를 저장해놨다가 큐 사이즈 만큼을 진행해주고 나면된다.
예를 들어 K=1 일때 큐 size 는 1이고 K=2 일때 size는 4, K=4 일때 size = 8 이다.
K 값이 바뀔 때마다 calc 함수에서 최대 서비스할 수 있는 집의 개수를 세서 리턴한다.
import java.io.*;
import java.util.*;
public class Solution {
static class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int N,M,max;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static int[][] city;
static Queue q = new LinkedList();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
city = new int[N][N];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
city[i][j] = Integer.parseInt(st.nextToken());
}
}
max = 0;
//모든칸 탐색
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
bfs(i,j);
}
}
System.out.println("#"+tc+" "+max);
}
}
static void bfs(int i, int j) {
boolean check[][] = new boolean[N][N];
q.add(new Pair(i,j));
check[i][j] = true;
int homecnt = 0;
int k = 1;
int size = q.size(); //처음 큐 사이즈 저장( 1값을 저장)
while(!q.isEmpty()) {
//K 값이 증가할 때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
homecnt = calc(k++, check);
if(max < homecnt) {
max = homecnt;
}
size = q.size(); //단계별로 진행하기 위해서 매번 들어가있는 큐사이즈를 구해준다
while(size-- > 0) { //size 만큼 탐색 진행
Pair p = q.remove();
int x = p.x;
int y = p.y;
int cnt = 0;
for(int l=0; l<4; l++) {
int nx = x+dx[l];
int ny = y+dy[l];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(check[nx][ny]) continue;
q.add(new Pair(nx,ny));
check[nx][ny] = true;
if(city[nx][ny] == 1) cnt+= 1;
}
}
}
}
static int calc(int k, boolean[][] check) {
int homecnt = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(check[i][j] && city[i][j] == 1) {
homecnt += 1; //방문 한 곳(서비스 영역)중에 집이 있으면 집의 수를 count
}
}
}
int cost = (k*k)+((k-1)*(k-1));
int profit = homecnt*M - cost;
if(profit >= 0) //마이너스 값이 아닌 이상 손해가 아니다
return homecnt;
else
return 0;
}
}
두 번째 풀이
모든칸에 대해서 K값에 따른 최대 집의 개수를 구해준다.
집의 K값의 모양을 구하는식은
현재 칸이 x, y 라고 했을 때 모든 칸 i, j 에 대해서 계산해준다.
K = |i-x| + |j-y| 를 계산해서 다음과 같이 구할 수 있다.
K=2 일때 위의 식을 사용하면 다음과 같이 된다.
2
2
1
2
2
1
(x,y)
1
2
2
1
2
2
import java.io.*;
import java.util.*;
public class Solution {
static int N,M,max;
static int[][] city;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int tc=1; tc<=T; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
city = new int[N][N];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++) {
city[i][j] = Integer.parseInt(st.nextToken());
}
}
max = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
calc(i,j);
}
}
System.out.println("#"+tc+" "+max);
}
}
static void calc(int x, int y) {
for (int k = 0; k < N + 2; k++) {
//K가 최대 N*N 칸을 모두 채우는 범위까지 진행
int homecnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int nx = Math.abs(i - x);
int ny = Math.abs(j - y);
if (nx + ny < k && city[i][j] == 1) {
//현재 K 일때의 서비스 영역이고, 집이 있으면 집의 수를 count 해준다.
homecnt++;
}
}
}
int profit = (homecnt * M) - (k * k + (k - 1) * (k - 1)); //수익 계산
if (profit < 0)
continue;
else
max = Math.max(homecnt, max); //손해를 보지 않으면 집의 수를 최댓값과 비교하여 더 크면 저장.
}
}
}
