어흥

문제 링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 1. 주의할 점 - 5가지 유형의 테트로미노 중 'ㅗ'모양을 제외하고는 DFS로 찾을 수 있다. - 'ㅗ' 형태의 테트..

문제 링크: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A Set을 사용한다 이유: A가 2배씩 증가한다고 해도 30개만 들어간다(2^30>10억) + 10*A+1의 경우 그보다 적게 들어간다 #include #include #include using namespace std; struct info { long long idx; int va..

문제 링크: https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 www.acmicpc.net 1. 주의할 점 - 위상정렬이 1개가 아니다 2. 구현 - 모든 Node의 작업이 끝나는 시간의 최댓값을 result 배열에 저장..

문제 링크: https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다. www.acmicpc.net 1. 주의할점 - Row와 Col의 범위가 1~100이다 - 시간제한: 2초 결론 : DFS만 사용할 경우 TLE가 날 확률이 크다 -> 메모라이즈 이용 2. 구현 - dp배열 구성: y,x,몇번째 글자로 방문했는지(idx) 용도: 메모라이즈 - arr배열의 원소가 찾고자 ..

문제 링크: https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 주의할 점 - B가 최대 1000억까지 증가할 수 있다(단순 연산만 해도 100초) - 시간 제한: 1초 - 행렬의 원소는 매 계산마다 MOD 1000 한 결과를 보유한다 2. 해결법 - B를 logB만큼 줄여서 1초내에 연산을 끝내도록 한다 3. 함수 기능 - mul 함수: 2차행렬 X 2차행렬을 위한 함수 - pow 함수: v^B 의 결과를 돌려준다 #define MOD 1000 #incl..