swanzzz 님의 블로그

[백준] 9466 텀 프로젝트 - 골드

[오늘의 문제]https://www.acmicpc.net/problem/9466[오늘의 학습 키워드]DFS깊이 우선 탐색그래프 탐색그래프 이론구현1. 문제설명 학생들이 각자 원하는 팀이 있습니다. 위 그림에서 1번 학생은 3번 학생과 팀을 원하고 3번 학생은 혼자 팀을 하기 원합니다. 이 경우 3번 학생이 3번을 선택하였기 때문에 3번 학생혼자 프로젝트를 실시하고 1번 학생을 팀을 이루지 못했습니다. 2번의 경우 1번을 원하지만 1번은 이미 3번을 원했기에 2번도 팀을 이루지 못합니다. 3번의 경우 팀을 이뤘고 4번은 7번을 7번은 6번을 6번은 4번을 원하고 있습니다. 각각 원하는 사람이 겹치지 않고 6번이 4번을 선택했을 때 4번은 다시 7번을 선택하는 사이클이 완성되었으니 이 3명은 팀을 이뤘습니..

[백준] 5427 불 - 골드 4

[오늘의 문제]https://www.acmicpc.net/problem/5427[오늘의 학습 키워드]너비 우선 탐색그래프 탐색, 그래프 이론구현격자 그래프1. 문제설명 상근이는 빌딩에서 탈출하려 합니다. 빌딩의 크기는 각각 N, M 으로 주어지며 상근이의 위치와, 불이 난 곳, 벽, 빈 공간의 정보가 2차원 배열에 담겨 주어집니다. 불이 매 초마다 4방향으로 번지기 시작할 때 상근이가 빌딩에서 탈출이 가능하다면 탈출에 걸린 시간을 탈출이 불가능하다면 IMPOSSIBLE을 반환하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 256MB테스트 케이스는 최대 100개1 ≤ N, M ≤ 10002. 접근방식저는 우선 빌딩에 불을 모두 지르고 상근이가 탈출이 가능한지를 판별하였습니다. 불..

[오늘의 문제]https://www.acmicpc.net/problem/1600[오늘의 학습 키워드]너비 우선 탐색구현그래프 탐색, 그래프 이론격자 그래프1. 문제설명 동물원을 탈출한 원숭이가 0, 0 좌표에 존재합니다. 이 원숭이가 N, M 좌표로 이동하려고 하는데 말이 되고 싶어 말처럼 이동이 가능합니다. 말처럼 이동하는데는 최대 K번 이동이 가능하고 그 이후에는 인접한 4방향으로 이동이 가능합니다. 격자판에 정보가 주어질 때, 원숭이가 최소한의 동작으로 0, 0 좌표에서 N, M 좌표로 이동하는 방법을 구하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 256MBN과 M은 1이상 200이하의 자연수K는 0이상 30이하의 정수격자판에 주어진 정보 0은 평지, 1은 장애물2. 접근방식이 문제를 해..

[오늘의 문제]https://www.acmicpc.net/problem/2146[오늘의 학습 키워드]너비 우선 탐색BFS구현그래프 탐색, 그래픈 이론격자 그래프1. 문제설명 좌표평면에 지도의 정보가 주어집니다. 0은 바다, 1은 육지를 의미할 때 현재 육지와 다른 육지를 잇는 다리를 놓으려고 합니다. 이 다리를 놓을 때 가장 적은 비용이 들도록 가장 짧은 다리 하나만 설치한다고 합니다. 육지와 다른 육지를 잇는 다리의 길이가 가장 짧은 경우를 구해 출력하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 192MBN(100이하의 자연수)0은 바다, 1은 육지항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.2. 접근방식 문제를 보면 육지와 다른 육지를 잇는 최대한 짧은 다리를 놓으려 합니다. 그..

[오늘의 문제]https://www.acmicpc.net/problem/2011[오늘의 학습 키워드]DP구현1. 문제설명 A를 1, B를 2, Z를 26 이라고 암호화 하였습니다. 첫째 줄에 5000자리 이하의 암호가 주어질 경우 이 암호로 만들 수 있는 모든 경우의 수를 찾아 출력하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 128MB첫째 줄에 5000자리 이하의 암호가 주어진다.정답이 매우 크니 1000000으로 나눈 나머지를 출력2. 접근방식굉장히 어려운 문제 였습니다. 문제를 풀기 위해서는 각 숫자를 자릿수의 개념으로 접근해 보아야 합니다. 예시로 25114 를 복호화 하는 과정을 거쳐 경우의 수를 찾아 보겠습니다. 우선 25114 중 한자리만 들어온 경우를 살펴보죠..

[오늘의 문제]https://www.acmicpc.net/problem/1965[오늘의 학습 키워드]DP구현1. 문제설명 일렬로 늘어선 상자에 순서대로 상자를 넣습니다. 왼쪽에 있는 상자가 오른쪽에 있는 상자들 중 하나에 들어갈 수 있는데 상자는 크기가 달라서 자신보다 크기가 큰 상자에만 들어갈 수 있습니다. 1 5 2 3 7 크기의 상자가 늘어선 경우 1 2 3 7 순서로 상자를 넣는다면 최대 4개의 상자를 넣을 수 있죠 이런 방식으로 상자의 크기가 주어질 때, 한번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 만들어야 합니다.[제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 10002. 접근방식 문제가 저번에 풀었던 가장 긴 증가하는 부분 수열 문제와 비슷합니다. 현재 상자를 기..

[오늘의 문제] https://www.acmicpc.net/problem/9461[오늘의 학습 키워드]DP구현1. 문제설명 삼각형이 위 그림과 같은 모양으로 계속 추가되는 수열의 형태를 띄고 있습니다. 주어진 그림에서 삼각형의 가장 긴 변의 길이를 구하려고 하는데 그 변에 길이가 k일때 그 변에 길이가 k인 정삼각형을 추가합니다. 이런식으로 N회 반복을 수행할 때 N번째 삼각형의 변의 길이를 구하는 프로그램을 만드는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 128MB1 ≤ N ≤ 1002. 접근방식 이번 문제는 굉장히 쉽게 해결할 수 있습니다. 주어진 문제에서 P(1) 부터 P(10) 까지의 변의 길이가 주어집니다. 그 길이는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 라고 합니다. 그..

[오늘의 문제]https://www.acmicpc.net/problem/9465[오늘의 학습 키워드]DP구현1. 문제설명 주어진 스티커는 낡은 스티커라 하나의 스티커를 떼면 주변에 인접한 4방향의 스티커가 찢어져 사용할 수 없다. 따라서 스티커별로 점수를 매겨서 점수의 합이 가장 높아지게끔 스티커를 뜯으려 한다. N이 주어질 때, 2 x N 크기의 스티커의 점수의 최댓값을 구하는 프로그램을 작성하는 문제입니다.[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ N ≤ 100,0002. 접근방식 이번 문제를 해결하기 위해서는 점화식을 세우는 방식이 중요합니다. 스티커가 2 x N 장 주어질 때 스티커를 선택하는 방법중 최대값을 구하는 방법을 선택해야 합니다. N이 1이 주어진 경우부터 살펴 보겠습니다. ..

[오늘의 문제]https://www.acmicpc.net/problem/2133[오늘의 학습 키워드]DP구현1. 문제설명 3 x N 크기의 벽을 2x1 타일과 1x2 타일로 채우는 경우의 수를 구하는 문제 입니다. 타일의 세로 크기가 3으로 고정되어 있고 주어진 타일은 모두 2크기의 타일이므로 N이 홀수가 될 때는 타일을 제대로 채울 수 없습니다. [제한사항]시간 제한 2초메모리 제한 128MB1 ≤ N ≤ 302. 접근방식 문제를 해결하기 위해 우선 힌트를 살펴 보았습니다. 위 그림은 3 x 12 크기의 벽을 채우는 경우의 수 중 1개를 예시로 보여준 그림 입니다. 여기서 생각해 볼 수 있는 것은 1. 짝수마다 타일을 채울 수 있다. 2. 기본적으로 반복되는 기본 모양이 존재한다. 3. 규칙을 깨는 ..

[오늘의 문제]https://www.acmicpc.net/problem/1309[오늘의 학습 키워드]DP구현1. 문제설명 가로로 2칸 세로로 N칸인 동물원에 사자를 배치하는 경우의 수를 구하는 문제 입니다. 경우의 수에는 사자를 1마리, 2마리 ,,, N 마리 등 다양한 경우의 수가 존재하는데 사자를 아예 배치하지 않는 것도 경우의 수 중 하나라고 합니다.[제한사항]시간 제한 2초메모리 제한 128MB1≤ N ≤100,000 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 2. 접근방식이 문제는 점화식만 세우면 쉽게 해결할 수 있습니다. 우선 동물원 울타리가 1칸만 주어지는 경우를 살펴보죠 1칸이 주어진다면 넣을 수 잇는 경우의 수는 다음과 같습니다. 사자를 아예 넣지 않는 ..