King of the Jungle Lion

문제링크:1014번: 컨닝 (acmicpc.net) 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 이 문제는 교실의 상태가 최대 10*10 상태로 주어졌을때, 조건 내에 각 위치에 학생들을 최대로 앉힌 수를 구하는 문제이다. 조건은 1. 교실의 책상 N*M 칸중 책상이 부숴져 앉을 수 없는 칸이 있다. 2. 학생들은 컨닝을 할 수 있기에 학생들은 양 옆에 나란히 앉을 수 없고, 한칸 앞의 대각선 방향에 앉을 수 없다. 나는 각 행의 학생 상태를 비트마스킹으로 표현하고 0행부터 N-1행까지 DP로 최대 학생 수를 탐색하여 문..

문제링크: 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 제한 무게가 있는 배낭에 물품 당 무게, 가치가 각각 주어진 물품을 가장 효율적으로 넣는 문제이다. 이 문제는 DP를 활용하여 풀 수 있었다. 나는 1차원 배열의 DP를 사용해서 풀었지만 인터넷을 보니 2차원 배열의 DP를 사용해 푸는 방법도 있었다. 그런데 1차원 배열을 사용하는것이 더 간단하고 메모리나 시간복잡도 상에서도 ..

문제링크:9465번: 스티커 (acmicpc.net) 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이 문제는 스티커가 2행 n열로 배치되어 있고, 스티커가 각각 점수를 가진다 했을때, 스티커를 하나 떼기로 정하면 상하좌우 4방면의 스티커는 뗄 수 없어지는 조건에서 뗀 스티커의 총 최대 점수 합을 구하는문제이다. 보통 행렬이 있고 상하좌우 등의 조건이 있으면 bfs를 사용했지만 n이 100000으로 매우 크고 행이 2행밖에 되지 않아 다른 방법을 생각해야 했다. import sys T=int(sy..