주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
동적 계획법
모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.
더 자세한 내용은 링크를 남겨두겠습니다.
동적 계획법 - 위키백과, 우리 모두의 백과사전
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분
이 문제에 핵심은
1. 주어진 배열에 대하여 연산 및 ∂을 받아서 배열을 변화시킵니다.
2. R개의 연산이 종료된 뒤 배열에 값들을 결과로 출력합니다.
문제에서 ∂에 대한 내용을 설명하면
∂의 값에 따라서 배열의 구역을 나눕니다.
n = ∂이라고 가정하고 나누는 크기는 2ⁿ의 크기로 구역을 나눕니다.
문제에 그림에서 표현한 것처럼 ∂의 값에 따라 구역을 나누는 것을 확인하실 수 있습니다.
연산에 대해서 알아보면
연산1.(상하반전)
배열의 구역들을 기준으로 상하반전이 일어난다.
∂에 값에 따라 구역을 나눈 크기를 이용하여 배열에 각 구역에 상하반전을 수행하도록 합니다.
연산2.(좌우반전)
배열의 구역들을 기준으로 좌우반전이 일어난다.
∂에 값에 따라 구역을 나눈 크기를 이용하여 배열에 각 구역에 좌우반전을 수행하도록 합니다.
연산3.(오른쪽 90º 회전)
배열의 구역들을 기준으로 오른쪽 90º 회전이 일어난다.
만약 3×3배열에서 값을 오른쪽으로 90º로 회전할 때
(0, 0) -> (0, 2)
(1, 1) -> (1, 1)
(2, 1) -> (1, 0)
점화식 = (n, m) -> (m, col최대값 - n)
점화식을 이용해서 각 구역의 시작점을 기준으로 90º 회전을 진행하여 변경해줍니다.
연산4.(왼쪽 90º 회전)
배열의 구역들을 기준으로 왼쪽 90º 회전이 일어난다.
만약 3×3배열에서 값을 왼쪽으로 90º로 회전할 때
(0, 0) -> (2, 0)
(1, 1) -> (1, 1)
(2, 1) -> (1, 2)
점화식 = (n, m) -> (row최대값-m, n)
점화식을 이용해서 각 구역의 시작점을 기준으로 90º 회전을 진행하여 변경해줍니다.
연산 5~8는 구역을 하나의 배열 값으로 생각하고 변경을 진행합니다.
연산5.(상하반전)
구역을 하나의 값으로 생각하고 상하반전이 일어난다.
∂에 값에 따라 구역을 나눈 크기를 이용하여 배열에 구역을 하나의 값으로 상하반전을 수행하도록 합니다.
연산6.(좌우반전)
구역을 하나의 값으로 생각하고 좌우반전이 일어난다.
∂에 값에 따라 구역을 나눈 크기를 이용하여 배열에 구역을 하나의 값으로 좌우반전을 수행하도록 합니다.
연산7.(오른쪽 90º 회전)
배열의 구역을 하나의 값으로 생각하고 오른쪽 90º 회전이 일어난다.
만약 3×3배열에서 값을 오른쪽으로 90º로 회전할 때
(0, 0) -> (0, 2)
(1, 1) -> (1, 1)
(2, 1) -> (1, 0)
점화식 = (n, m) -> (m, col최대값 - n)
점화식을 이용해서 각 구역의 시작점을 회전하고 회전한 시작점을 중심으로 변경합니다.
연산8.(왼쪽 90º 회전)
배열의 구역들을 기준으로 왼쪽 90º 회전이 일어난다.
만약 3×3배열에서 값을 왼쪽으로 90º로 회전할 때
(0, 0) -> (2, 0)
(1, 1) -> (1, 1)
(2, 1) -> (1, 2)
점화식 = (n, m) -> (row최대값-m, n)
점화식을 이용해서 각 구역의 시작점을 회전하고 회전한 시작점을 중심으로 변경합니다.
R번 연산을 통해 배열의 값들을 변경한 뒤 배열의 값들을 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer를 이용하여 배열의 정보 및 N,R,연산의 정보를 저장하였습니다.
- 연산에 따라 배열의 변경하는 함수를 호출하는 cal 함수를 실행하였습니다.
- R번 연산을 수행한 후 배열의 값들을 BufferedWriter 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- cal함수는 연산 번호에 맞는 함수 호출 및 ∂에 대한 구역 크기를 구하였습니다.
- one, two, ...., eight 함수들은 각 연산의 대한 배열의 변경을 진행하는 함수입니다.
import java.io.*;
import java.util.*;
public class Main {
static int N,R;
static int[][] arr; //입력되는 배열 및 변경되는 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
int size = (int)Math.pow(2,N);
arr = new int[size][size];
//배열의 값 저장
for(int i=0;i<size;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<size;j++)
arr[i][j] = Integer.parseInt(st.nextToken());
}
//연산의 값 저장
for(int i=0;i<R;i++) {
st = new StringTokenizer(br.readLine()," ");
int k = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
cal(k,l,size); //배열 변경 함수 실행
}
//R번 연산으로 변경된 배열 BufferedWriter 저장
for(int i=0;i<size;i++) {
for(int j=0;j<size;j++)
bw.write(arr[i][j] + " ");
bw.newLine();
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//연산에 대한 함수를 호출하는 함수
static void cal(int k, int l, int size) {
int arrDiv = (int)Math.pow(2, l); //∂에 따른 구역의 크기 구하기
//연산 번호에 따른 함수 호출
if(k==1) {
one(arrDiv,size);
}else if(k==2)
two(arrDiv,size);
else if(k==3)
three(arrDiv,size);
else if(k==4)
four(arrDiv,size);
else if(k==5)
five(arrDiv,size);
else if(k==6)
six(arrDiv,size);
else if(k==7)
seven(arrDiv,size);
else
eight(arrDiv,size);
}
//연산 1.
static void one(int div,int size) {
int tempDiv = div/2;
for(int i=div;i<=size;i += div) {
int minus = 0;
for(int j = i-div;j<i-tempDiv;j++) {
minus++;
for(int s = 0;s<size;s++) {
int temp = arr[j][s];
arr[j][s] = arr[i-minus][s];
arr[i-minus][s] = temp;
}
}
}
return;
}
//연산 2.
static void two(int div, int size) {
int tempDiv = div/2;
for(int i=div;i<=size;i += div) {
int minus = 0;
for(int j=i-div;j<i-tempDiv;j++) {
minus++;
for(int s=0;s<size;s++) {
int temp = arr[s][j];
arr[s][j] = arr[s][i-minus];
arr[s][i-minus] = temp;
}
}
}
}
//연산 3.
static void three(int div, int size) {
int[][] temp = new int[size][size];
for(int i=0;i<size;i++) {
for(int j = 0;j<size;j++) {
temp[(i/div)*div + j%div][((j/div+1)*div)-1 - i%div] = arr[i][j];
}
}
arr = temp;
return;
}
//연산 4.
static void four(int div, int size) {
int[][] temp = new int[size][size];
for(int i=0;i<size;i++) {
for(int j=0;j<size;j++) {
temp[(i/div+1)*div -1 - j%div][(j/div)*div + i%div] = arr[i][j];
}
}
arr = temp;
return;
}
//연산 5.
static void five(int div, int size) {
for(int i=0;i<size/2;i++) {
int row = ((size-i-1)/div)*div+i%div;
for(int j=0;j<size;j++) {
int temp = arr[i][j];
arr[i][j] = arr[row][j];
arr[row][j] = temp;
}
}
return;
}
//연산 6.
static void six(int div,int size) {
for(int i=0;i<size/2;i++) {
int col = ((size-1-i)/div) * div + i%div;
for(int j=0;j<size;j++) {
int temp = arr[j][i];
arr[j][i] = arr[j][col];
arr[j][col] = temp;
}
}
return;
}
//연산 7.
static void seven(int div, int size) {
int[][] temp = new int[size][size];
for(int i=0;i<size;i++) {
for(int j=0;j<size;j++) {
temp[(j/div)*div + i%div][((size-1-i)/div)*div + j%div] = arr[i][j];
}
}
arr = temp;
return;
}
//연산 8.
static void eight(int div, int size) {
int[][] temp = new int[size][size];
for(int i=0;i<size;i++) {
for(int j=0;j<size;j++) {
temp[((size-1-j)/div)*div + i%div][(i/div)*div + j%div] = arr[i][j];
}
}
arr = temp;
return;
}
}'백준' 카테고리의 다른 글
| [백준] 단계별로 풀어보기(단계:29, 트리,JAVA)11725번, 트리의 부모 찾기 (0) | 2022.05.26 |
|---|---|
| [백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)16928번, 뱀과 사다리 게임 (0) | 2022.05.25 |
| [백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)24445번, 알고리즘 수업 - 너비 우선 탐색 2 (0) | 2022.05.24 |
| [백준] code.plus(시뮬레이션과 구현,JAVA)16967번, 배열 복원하기 (0) | 2022.05.21 |
| [백준] 단계별로 풀어보기(단계:25, 그래프와 순회,JAVA)24444번, 알고리즘 수업 - 너비 우선 탐색 1 (0) | 2022.05.20 |
댓글