본문 바로가기
728x90

Algorithm68

백준 2665번 미로만들기 1. 문제 설명 문제 링크 n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다. 시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. 아래 그림은 n=8인 경우의 한 예이다. 위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시.. 2023. 1. 23.
백준 14500번 테트로미노 1. 문제 설명 문제 링크 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하.. 2023. 1. 21.
백준 2636번 치즈 1. 문제 설명 문제 링크 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 와 같이 된다. 원래 치즈 모양 다시 한 시간 후에는 에서 ‘c’로 표시된 부분이 녹아 없어져서 과 같이 된다. 한 시간 후의 치즈 모양.. 2023. 1. 18.
JAVA Basic Dictionary & Map 클래스 JAVA Basic : Dictionary & Map 클래스 Map 클래스와 일반 배열과의 차이점 패키지 java.util java.lang 클래스 정의 Map ht = new HashMap(); String[] array = new String[n] ← n자리수의 배열 정의 크기 크기가 정해져 있지 않다. 확장성 용이 한번 배열클래스를 정의하면 크기 고정. 순서 순서가 없다. 순서가 있다. 입출력형태 Key-Value 형태로 입출력을 한다. 배열의 Index 숫자를 지정해서 입출력을 한다. 반복출력 시 순서없이 뒤죽박죽 출력된다.Key와 Value는 한 쌍이기때문에 Key&Value는 안섞인다. 배열 Index번호대로 차례대로 출력된다. Map의 주요 메소드 Map ht = new HashMap(); .. 2023. 1. 17.
백준 1990번 소수인팰린드롬 1. 문제 설명 문제 링크 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오. 입력 입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다. 출력 첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다. 2. 코드 import sys input = sys.stdin.readline # 입.. 2023. 1. 15.
백준 11726번 2 * n 타일링 1. 문제 설명 문제 링크 ×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 2. 코드 import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n + 2]; dp[1] = 1; dp[2] = 2; for (in.. 2023. 1. 13.
728x90

티스토리툴바