알고리즘매일매일

문제

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다.
M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다.
죽은 파리의 개수를 구하라!

[제약 사항]
1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

풀이

1. n과 m의 범위가 작기 때문에 모든 경우를 해줘도 될 것 같다.
2. i <= (n-m), j<=(n-m) 의 범위에서 모든 (i,j)에 대하여 (i,j)를 시작점으로 하는 M X M 크기의 사각형 내의 파리의 합을 구해준다.
3. 합을 매번 최대 값과 비교하여 최댓값을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int max, n, m;
	static int[][] area;
	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());
			area = new int[n][n];
			for(int i=0; i<n; i++) {
				st = new StringTokenizer(br.readLine()," ");
				for(int j=0; j<n; j++) {
					area[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			max = 0;
            //모든 경우의 수를 구한다.
			for(int i=0; i<=n-m; i++) {
				for(int j=0; j<=n-m; j++) {
					getMax(i,j);
				}
			}
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void getMax(int x, int y) {
		int sum = 0;
		for(int i=x; i<x+m; i++) {
			for(int j=y; j<y+m; j++) {
				sum += area[i][j];
			}
		}
		if(max < sum) max = sum;
	}

}

문제

크기가 N인 파스칼의 삼각형을 만들어야 한다.
파스칼의 삼각형이란 아래와 같은 규칙을 따른다.
1. 첫 번째 줄은 항상 숫자 1이다.
2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.
N이 4일 경우,
 

N을 입력받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.

풀이

1. n*n 배열에 저장하여 푼다.
2. (0,0)부터 시작하여 행이 i번째 일 때, 열(j)은 i번째 까지 존재한다.
   1. 각 행에서 0번 index 이거나 마지막 index(i번째)인 경우에는 1.
   2. 그 외의 i행 j열의 값은 i-1행의 j-1열값과 i-1행의 j열 값을 더한 값이다.

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());
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[][] arr = new int[n][n];
			arr[0][0] = 1;
			for(int i=1; i<n; i++) {
				for(int j=0; j<=i; j++) {
					if(j==0 || j==i) {
						arr[i][j] = 1;
					} else {
						arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
					}
				}
			}
			System.out.println("#"+tc);
			for(int i=0; i<n; i++) {
				for(int j=0; j<=i; j++) {
					System.out.print(arr[i][j]+" ");
				}
				System.out.println();
			}
		}
	}

}

문제

패턴에서 반복되는 부분을 마디라고 부른다. 문자열을 입력받아 마디의 길이를 출력하는 프로그램을 작성하라.

풀이

1. 반복되는 패턴을 저장할 String 변수 pattern의 길이를 하나씩 늘려주며 비교한다.
2. i-1번째까지를 pattern 변수에 넣었을때 기존에 입력받은 문자열의 i번째부터 길이 i만큼을 잘라서 새로 tmp 만큼에 넣는다.
3. pattern과 tmp 가 같으면 pattern변수의 길이를 출력하고 종료.

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());
		for(int tc=1; tc<=T; tc++) {
			String s = br.readLine();
			for(int i=1; i<=s.length(); i++) {
				String pattern = s.substring(0, i);
				String tmp = s.substring(i,i+i);
				if(pattern.equals(tmp)) {
					System.out.println("#"+tc+" "+pattern.length());
					break;
				}
			}			
		}	
	}
}

문제

입력으로 정수 N 이 주어졌을 때, 1~N 까지의 숫자를

게임 규칙에 맞게 출력하는 프로그램을 작성하라.

박수를 치는 부분은 숫자 대신, 박수 횟수에 맞게 “-“ 를 출력한다.

여기서 주의해야 할 것은 박수 한 번 칠 때는 - 이며, 박수를 두 번 칠 때는 - - 가 아닌 -- 이다. 

N은 10이상 1,000이하의 정수이다. (10 ≤ N ≤ 1,000)

풀이

1.  먼저 3,6,9를 포함하는지 확인하기 위해 1부터 n까지의 숫자를 String으로 변환한다.
2. String s에 3이나, 6, 9가 포함되어 있는 경우에 3,6,9 는 - 로 바꿔주고, 나머지 숫자는 없애준다.

import java.util.*;
import java.io.*;
public class Solution {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=1; i<=n; i++) {
            String s = Integer.toString(i);
            if(s.contains("3") || s.contains("6") || s.contains("9")) {
                s = s.replace("3", "-");
                s = s.replace("6", "-");
                s = s.replace("9", "-");
                s = s.replace("1", "");
                s = s.replace("2", "");
                s = s.replace("4", "");
                s = s.replace("5", "");
                s = s.replace("7", "");
                s = s.replace("8", "");
                s = s.replace("0", "");
            }
            System.out.print(s+" ");
        }
    }
}