응파카 성장일지

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 두 개의 2차원 배열 board 와 check 를 만들어 보자, if 종이 전체가 같은 색깔로 칠해져 있지 않다면 - 가로와 세로 중간을 잘라서 4등분 한다. - 이를 반복 단일 색상의 색종이 수를 색상별로 출력하면 되는 문제이다 즉, 다음 과정을 반복한다 1. 영역의 전체 색상이 같은지 확인한다 if 같으면 해당 색상 count++ else 4등분하여 각 부분별로 문제..

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readL..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 배열 한 변의 길이는 2^N 한 변이 2^(N-1)인 사각형 4개로 나누어 왼쪽 위 - 오른쪽 위 - 왼쪽 아래 - 오른쪽 아래 순서 한 변의 길이가 2가 되었을 때 static int number 를 대입하면 됨 이후 board[r][c]의 값을 출력하면 된다 -> 메모리 초과 발생 board 전체를 recursion() 해서 그런 것으로 생각된다 r, c의 위치를 계속 추척해, 해당하는 영역만 recursion 할 필요가 있다 -> number++이..

10971번: 외판원 순회 2 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 행렬의 형태로 도시간 이동에 필요한 비용 주어짐 (이차원 행렬 사용) 도시의 수 N 입력받음 -> int[N][N] 행렬 W 생성 도시의 수가 2~10 이므로 이차원 배열 사용해도 시간초과 걱정은 없다. 이동이 불가능한 경우 비용은 0이다. solution() 을 재귀호출 하는 DFS 방식으로 해결 import java.io.BufferedReader; import java.io.IOExc..

16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 시간제한 2초로 충분하다고 생각 브루트 포스 방식으로 모든 경우의 수들 DFS 방식으로 건드린 다음 maxCount 를 출력하면 된다. 내구도와 무게 필드를 갖는 Egg 클래스를 만든다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java...

9663번: N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 제한시간 10초 - N X N 크기의 이차원 배열 체스판 board 사용 - N 개의 퀸이 주어졌을 때, 서로 공격할 수 없게 놓는 경우의 수 구하기 - 서로 공격할 수 있는지 없는지 확인하는 check 메서드 - 현재까지 놓은 퀸의 개수를 저장하는 queen - 퀸을 놓는 방법의 수 count - (i = 0 ~ N-1)(j = 0 ~ N-1) 상의 좌표 돌아다니며 DFS - 도중 queen == N 이 되면 count++, 백트래킹 => 시간초과로..

17136번: 색종이 붙이기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹, 브루트 포스 문제. 한 변의 길이가 1, 2, 3, 4, 5 인 정사각형 모양의 색종이를 한 변의 길이가 10 인 색종이 안에 붙이되, 다음 조건을 만족해야 한다. 1. 0이 적힌 칸에는 색종이가 있어서는 안된다. 2. 종이의 경계 밖을 나가서는 안된다. 3. 붙이는 종이들끼리 겹치면 안된다. 이 때 1이 적힌 모든 칸들을 붙이는데 필요한 색종이의 최소 개수를 구하면 된다. - 현재의 위치와 사용된 종이의 총 개수를..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[]..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ne..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 갖고있는 카드의 개수 N 을 입력받는다. 2. N개 만큼 숫자를 입력받는다. 3. 정수 M을 입력받는다. 4. 숫자 M개를 입력받는다. N 개의 배열을 돌면서 내부적으로 M 번의 탐색을 하는 것은 O(N^2)라는 엄청난 시간복잡도가 나오기에 HashMap 를 사용하여 쉽게 풀 수 있다. import java.io.BufferedReader; import ja..