https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
https://alwaysbemoon.tistory.com/225
[백준 20057, Java] 마법사 상어와 토네이도
문제 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격
alwaysbemoon.tistory.com
새롭게 블로그 참조하면서 코드를 다시 짜봣다..
아마 패인이 애초에 문제를 풀떄
토네이도 방향을 그냥 코드로 쉽게 구현할 수 있는데 어렵게 생각하고 모든 map에 화살표 방향을 넣어서 할려다가 망한것같다.
이번 문제를 보고 느낀건
1. 서쪽 남쪽 동쪽 북쪽 방향으로 이루어진다고했을때
(서쪽) (남쪽) (동쪽 동쪽) (북쪽 북쪽) (서쪽 서쪽 서쪽) (남쪽 남쪽 남쪽)
1 1 2 2 3 3 4 4 ...
이렇게 늘어나는데 이것을 잘생각했으면 아마 좀 도움이 됬을 것 같다.
2.배열을 잘사용하자
static int[] dx = {0,1,0,-1}; //토네이도의 x 이동 방향
static int[] dy = {-1,0,1,0}; //토네이도의 y 이동방향
static int[][] dsx =
{
{-1,1,-2,-1,1,2,-1,1,0},
{-1,-1,0,0,0,0,1,1,2},
{1,-1,2,1,-1,-2,1,-1,0},
{1,1,0,0,0,0,-1,-1,-2}
};
static int[][] dsy =
{
{1,1,0,0,0,0,-1,-1,-2},
{-1,1,-2,-1,1,2,-1,1,0},
{-1,-1,0,0,0,0,1,1,2},
{1,-1,2,1,-1,-2,1,-1,0}
};
이런것처럼 이런 배열들을 쉽게 사용해야 할줄 알아야 문제를 빨리 풀수 있고,
package Main;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
static int N;
static int[][] map;
static int[] dx = {0,1,0,-1}; //토네이도의 x 이동 방향
static int[] dy = {-1,0,1,0}; //토네이도의 y 이동방향
static int[][] dsx =
{
{-1,1,-2,-1,1,2,-1,1,0},
{-1,-1,0,0,0,0,1,1,2},
{1,-1,2,1,-1,-2,1,-1,0},
{1,1,0,0,0,0,-1,-1,-2}
};
static int[][] dsy =
{
{1,1,0,0,0,0,-1,-1,-2},
{-1,1,-2,-1,1,2,-1,1,0},
{-1,-1,0,0,0,0,1,1,2},
{1,-1,2,1,-1,-2,1,-1,0}
};
static int[] sandRatio = {1,1,2,7,7,2,10,10,5};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N=sc.nextInt();
map = new int[N][N];
for(int r=0;r<N;r++) {
for(int c=0;c<N;c++) {
map[r][c] = sc.nextInt();
}
}
System.out.println(simulatetornado(N/2, N/2));
}
public static int simulatetornado(int x, int y) {
int gooutsand = 0;
int currentX = x;
int currentY = y;
int movecount=1;
int direction=0;
boolean endflag = false;
while(!endflag) {
//1,1,2,2,3,3,4,4,5,5,6,6.... 이런식으로 증가
for(int i=0;i<2;i++) {
for(int j=0;j<movecount;j++) {
int moveX = currentX + dx[direction%4];
int moveY = currentY + dy[direction%4];
if(currentX == 0 && currentY == 0) {
// System.out.println("not working");
endflag = true;
break;
}
if(moveX >= 0 && moveX <N && moveY >=0 && moveY <N) {
int originsand = map[moveX][moveY];
// System.out.println("moveX: move Y:" + moveX +" " +moveY);
// System.out.println("originsand = map[moveX][moveY]:"+originsand+" "+map[moveX][moveY]);
int movedsand = 0;
for(int k=0;k<9;k++) {
movedsand += (originsand*sandRatio[k])/100;
if(moveX + dsx[direction%4][k] >= 0 && moveX + dsx[direction%4][k] < N && moveY + dsy[direction%4][k] >= 0 && moveY + dsy[direction%4][k] < N) {
// System.out.println("sandRatio[k]/100 * originsand:"+(originsand*sandRatio[k])/100);
map[moveX + dsx[direction%4][k]][moveY + dsy[direction%4][k]] += (originsand*sandRatio[k])/100;
// System.out.println("map[moveX + dsx[direction%4][k]][moveY + dsy[direction%4][k]]:"+map[moveX + dsx[direction%4][k]][moveY + dsy[direction%4][k]] );
}else {
gooutsand += (originsand*sandRatio[k])/100;
}
}
if(moveX + dx[direction%4] >= 0 && moveX + dx[direction%4] < N && moveY + dy[direction%4] >= 0 && moveY + dy[direction%4] < N){
map[moveX + dx[direction%4]][moveY + dy[direction%4]] += originsand - movedsand;
map[moveX][moveY] = 0;
}else {
gooutsand += originsand-movedsand;
}
}
currentX = moveX;
currentY = moveY;
// System.out.println("gooutsand:"+gooutsand);
// for(int row=0;row<N;row++) {
// for(int col=0;col<N;col++) {
// System.out.print(" "+map[row][col]);
// }
// System.out.println();
// }
// System.out.println();
}
direction += 1;
if(endflag) {
break;
}
}
movecount+=1;
}
return gooutsand;
}
}
이문제를 내가 직접 풀어보려고 했는데 지금 2시간 30분이 지나도 거의 풀것같은 느낌이 안들어서 포기하고 넘어간다
일단은 위의 블로그를 보고 좀 빠르게 풀어보자
내가 푸는방식은 너무 과도하게 시간이 오래걸리는방식이다.
package Main;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
/*
* 코딩방식
* 1.map[i][j]에 모래의 값을 넣는다.
* 2.map[N/2][N/2]부터 알고리즘이 시작되며
* (1) map[3][3]이 map[3][2]로 태풍이 이동했다고 해보자.
* (2) map[3][3]의 모래비율이 map[3][2]로 이동하며 이동했다.
* (3) map[3][3]의 바로 위에 작업을 하면 당연히 안되고 tempmap을 따로 만들어서 진행해야한다.
* (3) 모래바람이 뱀 형식으로 이동하는 것을 보면 1,1, 2,2 3,3 4,4 5,5 6,6 7 이렇게 이동하는 것을 볼수 있다.
*
*
* N = 3 일때 5번 (5 가 기본)
* N = 5 일때 13번 (5+8 이전에 비해 8 증가)
* N = 7 일때 21번 (5+8+8 이전에 비해 8 증가)
* N = 9 일때 29번 (5+8+8+8 이전에 비해 8증가)
*
* 즉 N+=2 일대마다 8씩 증가합니다.
*
*/
public static int N;
public static int[][] map;
public static int[][] tornadodirection;
//좌,하,우,상
public static int[] dx = {0,1,0,-1};
public static int[] dy = {-1,0,1,0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N=sc.nextInt();
map = new int[N][N];
tornadodirection = new int[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
map[i][j] = sc.nextInt();
}
}
simulate();
}
public static void simulate() {
tornadodirection();
int count=0;
int row=N/2;
int col=N/2;
while(count==N*N) {
if(tornadodirection[row][col] == 0) {
tornado(row, col, tornadodirection[row][col]);
}else if(tornadodirection[row][col] == 1) {
}else if(tornadodirection[row][col] == 2) {
}else if(tornadodirection[row][col] == 3) {
}
}
}
public static void tornado(int original_row, int original_col, int direction) {
int sandamount = map[original_row][original_col];
int alphaamount = sandamount - (int) ((sandamount * (0.02 + 0.1 + 0.07 + 0.01) * 2) + sandamount*0.05);
int destination_row = original_row + dx[direction];
int destination_col = original_col + dy[direction];
if(direction == 0) {
//상단부분
map[destination_row-2][destination_col] += sandamount*0.02;
map[destination_row-1][destination_col-1] += sandamount*0.1;
map[destination_row-1][destination_col] += sandamount*0.07;
map[destination_row-1][destination_col+1] += sandamount*0.01;
//중간부분
map[destination_row][destination_col-2] += sandamount*0.05;
//하단부분
map[destination_row+2][destination_col] += sandamount*0.02;
map[destination_row+1][destination_col-1] += sandamount*0.1;
map[destination_row+1][destination_col] += sandamount*0.07;
map[destination_row+1][destination_col+1] += sandamount*0.01;
//알파 부분
map[destination_row][destination_col-1] += alphaamount;
}else if(direction == 1) {
//상단부분
map[destination_row][destination_col-2] += sandamount*0.02;
map[destination_row-1][destination_col+1] += sandamount*0.1;
map[destination_row-1][destination_col] += sandamount*0.07;
map[destination_row-1][destination_col-1] += sandamount*0.01;
//중간부분
map[destination_row+2][destination_col] += sandamount*0.05;
//하단부분
map[destination_row+2][destination_col] += sandamount*0.02;
map[destination_row+1][destination_col+1] += sandamount*0.1;
map[destination_row+1][destination_col] += sandamount*0.07;
map[destination_row+1][destination_col-1] += sandamount*0.01;
//알파 부분
map[destination_row+1][destination_col] += alphaamount;
}if(direction == 2) {
//상단부분
map[destination_row-2][destination_col] += sandamount*0.02;
map[destination_row-1][destination_col+1] += sandamount*0.1;
map[destination_row-1][destination_col] += sandamount*0.07;
map[destination_row-1][destination_col-1] += sandamount*0.01;
//중간부분
map[destination_row][destination_col+2] += sandamount*0.05;
//하단부분
map[destination_row+2][destination_col] += sandamount*0.02;
map[destination_row+1][destination_col+1] += sandamount*0.1;
map[destination_row+1][destination_col] += sandamount*0.07;
map[destination_row+1][destination_col-1] += sandamount*0.01;
//알파 부분
map[destination_row][destination_col+1] += alphaamount;
}else if(direction == 3) {
//상단부분
map[destination_row][destination_col-2] += sandamount*0.02;
map[destination_row-1][destination_col+1] += sandamount*0.1;
map[destination_row-1][destination_col] += sandamount*0.07;
map[destination_row-1][destination_col-1] += sandamount*0.01;
//중간부분
map[destination_row-2][destination_col] += sandamount*0.05;
//하단부분
map[destination_row+2][destination_col] += sandamount*0.02;
map[destination_row+1][destination_col+1] += sandamount*0.1;
map[destination_row+1][destination_col] += sandamount*0.07;
map[destination_row+1][destination_col-1] += sandamount*0.01;
//알파 부분
map[destination_row-1][destination_col] += alphaamount;
}
}
public static void tornadodirection() {
//채우는 순서, 하, 우, 상, 좌
//아래쪽으로 가는 방향 채우기 : 1(위쪽,아래쪽을 먼저 채우고 왼쪽 오른쪽을 채워야합니다.)
for(int i=0;i<N/2;i++) {
for(int j=i+1;j<N-i-1;j++) {
tornadodirection[j][i] = 1;
}
}
//오른쪽으로 가는 방향 채우기 : 2
for(int i=N-1;i>=N/2;i--) {
for(int j=N-1-i;j<=i;j++) {
tornadodirection[i][j] = 2;
}
}
//위쪽으로 가는 방향 채우기 : 3
for(int i=N-1;i>N/2;i--) {
for(int j=i;j>=N-1-i;j--) {
tornadodirection[j][i] = 3;
}
}
//왼쪽으로 가는방향 채우기
for(int i=0;i<=N/2;i++) {
for(int j=i;j<N-i;j++) {
tornadodirection[i][j] = 0;
}
}
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
System.out.print(tornadodirection[i][j]);
}
System.out.println();
}
}
}
'알고리즘 > 삼성SW' 카테고리의 다른 글
| [삼성 SW 역량 테스트 기출 문제] 주사위 굴리기 2 - 레벨1 (0) | 2022.07.05 |
|---|---|
| [삼성 SW 역량 테스트 기출 문제] 마법사 상어와 비바라기 - 레벨1 (0) | 2022.07.04 |
| [삼성 SW 역량 테스트 기출 문제] 미세먼지 안녕! - 레벨1 (0) | 2022.04.26 |
| [삼성 SW 역량 테스트 기출 문제] 드래곤 커브 - 레벨1 (0) | 2022.04.05 |
| [삼성 SW 역량 테스트 기출 문제] 경사로 - 레벨1 (0) | 2022.03.15 |