응파카 성장일지

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..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net N개의 줄에 1~N 번의 포켓몬들이 입력된다. 문제 M개가 주어진다. 포켓몬 이름이 주어지면 번호를 말하고, 번호가 주어지면 포켓몬을 말한다. N의 범위가 1~100,000 이기에 - 배열 사용시 숫자에 대응되는 포켓몬을 찾는것은 빠를 수 있어도 - 포켓몬이 위치한 인덱스를 찾는 것은 O(N)의 시간복잡도로 인해 비효율적이다. 이를 해결하기 위해 String 배열과 M..