본문 바로가기
학부공부/Java_Basic

Chapter 8. Multidimensional Arrays(2)[Java Basic]

by sonpang 2021. 11. 6.
반응형

8.H - 게임: 커넥트포

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

커넥트포는 두명의 플레이어가 번갈아가며 7개의 열과 6개의 행으로 구분된 보드에 색깔로 구분된 말을 떨어 뜨리는 방식으로 진행되는 보드게임입니다.

Connect four is a two-player board game in which the players alternately drop colored disks into a seven-column, six-row vertically suspended grid, as shown below.

게임의 승리조건은 행, 열, 대각선 방향 중 하나로 본인의 말을 연속적으로 4개 배치하는 것입니다. 빨강R과 노랑Y순으로 게임이 진행되고, 말이 떨어지는 열의 번호가 입력으로 주어진다고 할때, 게임이 종료되는 순간의 보드를 모습을 출력하는 프로그램을 작성하세요. (게임은 승리조건을 만족하는 즉시 종료됩니다.)

The objective of the game is to connect four same-colored disks in a row, a column, or a diagonal before your opponent can do likewise. The program prompts the series of the dropping column number with a red or yellow disk alternately, and display the the board on the console.

 

INPUT

* Line 1 : 말이 떨어지는 열의 번호를 공백으로 구분해서 출력 (0~6범위의 42개의 정수)

 

OUTPUT

게임의 종료모습을 샘플처럼 출력

보드의 빈칸은 스페이스로 표시

 

SAMPLE INPUT

6 6 6 1 1 1 0 0 1 5 3 4 3 5 5 2 2 0 5 6 3 0 0 2 4 3 3 4 5 2 0 6 4 6 2 1 5 2 4 1 3 4

 

SAMPLE OUTPUT

 

R

YR RY

YYYR RR

YRRRRYY

RYYRYYR

 

import java.util.Scanner;
import java.lang.Math;
public class Main {
    private static boolean check(int data[][]){
        int i, j, n = 6, m = 7;
        for(i = 0; i < n || i == 0; i++){
            for(j = 0; j < m || j == 0; j++){
                if(j < m - 3)
                    if(data[i][j] == data[i][j+1] && data[i][j] == data[i][j+2]&& data[i][j] == data[i][j+3])
                        return true;
                if(i < n - 3)
                    if(data[i][j] == data[i+1][j] && data[i][j] == data[i+2][j]&& data[i+3][j] == data[i][j])
                        return true;
                if(i < n - 3 && j < m - 3)
                    if(data[i][j] == data[i+1][j+1] && data[i][j] == data[i+2][j+2]&& data[i][j] == data[i+3][j+3])
                        return true;
                if(i >= 3 && j < m - 3)
                    if(data[i][j] == data[i-1][j+1] && data[i][j] == data[i-2][j+2]&& data[i][j] == data[i-3][j+3])
                        return true;
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int result[][] = new int[6][7], i, j, count[] = new int[7], n[] = new int[42];
        for(i = 0; i < 6; i++)
            for(j = 0; j < 7; j++)
                result[i][j] = 3 + (int)(Math.random()*100);
        for(i = 0; i < 42; i++)
            n[i] = input.nextInt();
        for(i = 0; i < 42 && !check(result); i++)
            result[count[n[i]]++][n[i]] = i % 2;
        for(i = 5; i >= 0; i--){
            for(j = 0; j < 7; j++){
                if(result[i][j] != 0 && result[i][j] != 1)
                    System.out.print(" ");
                else System.out.print(result[i][j] == 0 ? 'R':'Y');
            }
            System.out.println();
        }
    }
}

 

 

8.I - 가장 큰 조각 2 (난이도:고급)

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

이진행렬이 주어졌을 때 1로채워진 가장 큰 정사각형 부분행렬을 찾으세요.

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

 

INPUT

* Line 1 : 행의개수N 열의개수M (N, M은 1~1,000범위의 정수)

* Line 2 ~ N+1 : 공백으로 구분된 M개의 0 또는 1

* N x M 원소중에 적어도 하나의 1은 존재

 

OUTPUT

* Line 1 : i j k

- i: 부분행렬의 시작행 (0부터시작)

- j: 부분행렬의 시작열 (0부터시작)

- k: 부분행렬의 한변의 크기

 

SAMPLE INPUT

6 5

0 1 1 0 1

1 1 0 1 0

0 1 1 1 0

1 1 1 1 0

1 1 1 1 1

0 0 0 0 0

 

SAMPLE OUTPUT

2 1 3

 

import java.util.Scanner;
import java.lang.Math;
public class Main {
    private static boolean check(int data[][], int x, int y, int s){
        int i;
        for(i = x; i < x + s; i++)
            if(data[i][y + s - 1] == 0)
                return false;
        for(i = y; i < y + s; i++)
            if(data[x + s - 1][i] == 0)
                return false;
        return true;
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), m = input.nextInt(), data[][] = new int[n][m], i, j, indexi = 0, indexj = 0, max = 1, s;
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                data[i][j] = input.nextInt();
        for(i = 0; i < n; i++){
            for(j = 0; j < m; j++){
                if(data[i][j] == 1){
                    for(s = 2; s < Math.min(n - i + 1, m - j + 1); s++){
                        if(data[i][j] == 1 && data[i + s - 1][j + s -1] == 1 && check(data, i, j, s)){
                            if(max < s){
                                max = s;
                                indexi = i;
                                indexj = j;
                            }
                        }
                        else
                            break;
                    }
                }
            }
        }
        System.out.println(indexi + " " + indexj + " " + max);
    }
}
반응형

 

8.J - 정사각형?

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

주어진 4개의 점이 정사각형인지 체크하는 프로그램을 작성하세요.

 

INPUT

* Line 1 : 테스트케이스 T (1~1,000)

* Line 2 ~ T+1 : 공백으로 구분된 4쌍의 좌표 값 (각 좌표값은 -100~100 범위의 정수)

 

OUTPUT

* Line 1 ~ T : 정사각형일 경우 square를 출력, 아닐 경우 not square를 출력

 

SAMPLE INPUT

3

0 0 0 2 2 0 2 2

0 0 4 0 2 2 2 -2

0 0 0 2 2 2 2 4

 

SAMPLE OUTPUT

square

square

not square

 

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), data[][] = new int[n][8], i, j, d[] = new int[6];
        for(i = 0; i < n; i++)
            for(j = 0; j < 8; j++)
                data[i][j] = input.nextInt();
        for(i = 0; i < n; i++){
            d[0] = (data[i][0] - data[i][2]) * (data[i][0] - data[i][2]) + (data[i][1] - data[i][3]) * (data[i][1] - data[i][3]);
            d[1] = (data[i][2] - data[i][4]) * (data[i][2] - data[i][4]) + (data[i][3] - data[i][5]) * (data[i][3] - data[i][5]);
            d[2] = (data[i][4] - data[i][6]) * (data[i][4] - data[i][6]) + (data[i][5] - data[i][7]) * (data[i][5] - data[i][7]);
            d[3] = (data[i][6] - data[i][0]) * (data[i][6] - data[i][0]) + (data[i][7] - data[i][1]) * (data[i][7] - data[i][1]);
            d[4] = (data[i][0] - data[i][4]) * (data[i][0] - data[i][4]) + (data[i][1] - data[i][5]) * (data[i][1] - data[i][5]);
            d[5] = (data[i][2] - data[i][6]) * (data[i][2] - data[i][6]) + (data[i][3] - data[i][7]) * (data[i][3] - data[i][7]);
            Arrays.sort(d);
            if(d[0] == d[1] && d[1] == d[2] && d[2] == d[3] && d[4] == d[5] && d[0] != d[4])
                System.out.println("square");
            else System.out.println("not square");
        }
    }
}

 

Wrong Answer
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), data[][] = new int[n][8], i, j, d[] = new int[6];
        for(i = 0; i < n; i++)
            for(j = 0; j < 8; j++)
                data[i][j] = input.nextInt();
        for(i = 0; i < n; i++){
            d[0] = (data[i][0] - data[i][2]) * (data[i][0] - data[i][2]) + (data[i][1] - data[i][3]) * (data[i][1] - data[i][3]);
            d[1] = (data[i][2] - data[i][4]) * (data[i][2] - data[i][4]) + (data[i][3] - data[i][5]) * (data[i][3] - data[i][5]);
            d[2] = (data[i][4] - data[i][6]) * (data[i][4] - data[i][6]) + (data[i][5] - data[i][7]) * (data[i][5] - data[i][7]);
            d[3] = (data[i][6] - data[i][0]) * (data[i][6] - data[i][0]) + (data[i][7] - data[i][1]) * (data[i][7] - data[i][1]);
            d[4] = (data[i][0] - data[i][4]) * (data[i][0] - data[i][4]) + (data[i][1] - data[i][5]) * (data[i][1] - data[i][5]);
            d[5] = (data[i][2] - data[i][6]) * (data[i][2] - data[i][6]) + (data[i][3] - data[i][7]) * (data[i][3] - data[i][7]);
            Arrays.sort(d);
            if(d[0] == d[1] && d[1] == d[2] && d[2] == d[3] && d[4] == d[5])
                System.out.println("square");
            else System.out.println("not square");
        }
    }
}

 

 

8.K - 가장 큰 조각 1

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

0과 1로 채워진 사각행렬이 주어졌을 때, 1로 채워진 가장 큰 부분 행렬을 찾는 프로그램을 작성하세요. (동일한 크기가 여러개 일 경우에는 i, j 우선순위로 가장 가까운 사각행렬을 출력)

Given a square matrix with the elements 0 or 1, write a program to find a maximum square submatrix whose elements are all 1s. Your program should prompt the user to enter the number of rows in the matrix. The program then displays the location of the first element in the maximum square submatrix and the number of the rows in the submatrix.

 

INPUT

* Line 1 : 행의개수N (N은 1~20범위의 정수)

* Line 2 ~ N+1 : 공백으로 구분된 N개의 0 또는 1

 

OUTPUT

* Line 1 : i j k

- i: 부분행렬의 시작행 (0부터시작)

- j: 부분행렬의 시작열 (0부터시작)

- k: 부분행렬의 크기

 

SAMPLE INPUT

5

1 0 1 0 1

1 1 1 0 1

1 0 1 1 1

1 0 1 1 1

1 0 1 1 1

 

SAMPLE OUTPUT

2 2 3

 

import java.util.Scanner;
public class Main {
    private static boolean check(int data[][], int x, int y, int s){
        int i;
        for(i = x; i < x + s; i++)
            if(data[i][y + s - 1] == 0)
                return false;
        for(i = y; i < y + s; i++)
            if(data[x + s - 1][i] == 0)
                return false;
        return true;
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), data[][] = new int[n][n], i, j, indexi = 0, indexj = 0, max = 1, s;
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                data[i][j] = input.nextInt();
        for(i = 0; i < n; i++){
            for(j = 0; j < n; j++){
                for(s = 2; s < n - (i > j ? i : j) + 1; s++){
                    if(data[i][j] == 1 && check(data, i, j, s)){
                        if(max < s){
                            max = s;
                            indexi = i;
                            indexj = j;
                        }
                    }
                    else
                        break;
                }
            }
        }
        System.out.println(indexi + " " + indexj + " " + max);
    }
}

 

 

8.L - 다각형의 부분넓이

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

4개의 정점을 가지는 볼록 다각형은 아래 그림처럼 4개의 삼각형으로 나누어 집니다. 볼록 다각형의 정점의 좌표 4개를 입력 받아, 4개의 삼각형의 넓이를 오름차순으로 정렬해서 출력하는 프로그램을 만드세요.

주의사항: 이미지에서는 시계 방향으로 데이터가 들어가지만 현재는 그렇지 않은 경우에 대한 문제가 추가되어 있습니다. 일반적인 경우(순서 무관한 입력)의 해결책을 찾아주시길 바랍니다.

A convex 4-vertex polygon is divided into four triangles, as shown in Figure 8.9. Write a program that prompts the user to enter the coordinates of four vertices and displays the areas of the four triangles in increasing order.

 

INPUT

* Line 1 : 테스트케이스 T (1~1,000)

* Line 2 ~ T+1 : 공백으로 구분된 4쌍의 좌표 값 (각 좌표값은 -100~100 범위의 정수)

 

OUTPUT

* Line 1 ~ T : 오름차순으로 정렬된 삼각형의 넓이 (소수점 2자리로 반올림)

 

SAMPLE INPUT

1

0 0 1 1 2 0 2 -1

 

SAMPLE OUTPUT

0.25 0.25 0.75 0.75

 

HING

크라메르 공식

헤론의 공식

 

import java.util.Scanner;
import java.lang.Math;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(), i, j;
        double data[][] = new double[n][10], s[][] = new double[n][4], discriminant, a, b, c, d, e, f, x1, x2, x3, x4, y1, y2, y3, y4;
        for(i = 0; i < n; i++)
            for(j = 0; j < 8; j++)
                data[i][j] = input.nextDouble();
        for(i = 0; i < n; i++){
            x1 = data[i][0]; x3 = data[i][2]; x2 = data[i][4]; x4 = data[i][6]; y1 = data[i][1]; y3 = data[i][3]; y2 = data[i][5]; y4 = data[i][7];;
            a = y1 - y2; b = x2 - x1; c = y3 - y4; d = x4 - x3; e = a * x1 + b * y1; f = c * x3 + d * y3;
            discriminant = a * d - b * c;
            data[i][8] = (e * d - b * f) / discriminant;
            data[i][9] = (a * f - e * c) / discriminant;
        }
        double side1, side2, side3, t;
        for(i = 0; i < n; i++){
            for(j = 0; j < 8; j+=2){
                x1 = data[i][j % 8]; y1 = data[i][(j + 1) % 8]; x2 = data[i][(j + 2) % 8]; y2 = data[i][(j + 3) % 8]; x3 = data[i][8]; y3 = data[i][9];
                side1 = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
                side2 = Math.sqrt(Math.pow(x2 - x3, 2) + Math.pow(y2 - y3, 2));
                side3 = Math.sqrt(Math.pow(x3 - x1, 2) + Math.pow(y3 - y1, 2));
                t = (side1 + side2 + side3) / 2;
                s[i][j/2] = Math.sqrt(t * (t - side1) * (t - side2) * (t - side3));
            }
            Arrays.sort(s[i]);
        }
        for(i = 0; i < n; i++)
            System.out.printf("%.2f %.2f %.2f %.2f\n", Math.round(s[i][0]*100)/100.0, Math.round(s[i][1]*100)/100.0, Math.round(s[i][2]*100)/100.0, Math.round(s[i][3]*100)/100.0);
    }
}

 

반응형
저작자표시 비영리 변경금지

'학부공부 > Java_Basic' 카테고리의 다른 글

Chapter 10. Object-Oriented Thinking(1)[Java Basic]  (0) 2021.11.06
Chapter 9. Objects and Classes[Java Basic]  (0) 2021.11.06
Chapter 8. Multidimensional Arrays(1)[Java Basic]  (0) 2021.11.06
Chapter 7. Single-Dimensional Arrays[Java Basic]  (0) 2021.11.05
Chapter 6. Methods[Java Basic]  (0) 2021.11.05

관련글

댓글

티스토리툴바