https://www.algospot.com/judge/problem/read/PI 풀이 제한시간 1초 (테스트케이스 50) = 케이스 한개당 대략 200만 시간복잡도 알고리즘 : DP 0번 idx 부터 N-l번 idx까지 돌면서 l자리짜리 문자열을 검사해서 최소의 난이도를 myLv에 기록해둔다.(l은 문제 조건에 맞게 3~5까지) 0번 idx 부터 3가지 경우(길이를 3 ~ 5로 하는경우)로 완전탐색하며 해당 길이 뒤의 idx로 이동한다. 길이가 불가능한 경우는 해당 길이에 해당하는 myLv에 INF 가 들어있다. 탐색하면서 idx부터 끝까지 탐색할 때 생성할 수 있는 최소 난이도를 DP 배열에 기록해두고 이를 활용한다. 이를 활용하면 완전탐색에 총 문자열의 길이만큼 들 거라고 생각했다. 최소로 만들 ..

https://www.acmicpc.net/problem/17472 풀이 알고리즘 : Prim's Algorithm (잘못 알고있는 걸 수도 있으니 확실히 다시 공부필요) 섬과 섬을 잇는 다리의 최소를 구하고 이를 완전탐색을 이용해서 구해보려는 생각이 제일 처음 들었지만 잠깐 생각해보았을 때 생각보다 구현방식이 잘 떠오르지 않았고 오히려 배웠던 프림알고리즘이 떠올랐고 모든 답을 빼놓지 않고 찾을 수 있는 방법이었다. (이 정확성 증명도 다시 한번 공부필요) 맵 전체를 돌면서 BFS를 수행해서 각 섬에 번호를 1부터 number까지 붙인다. 맵 전체를 행단위, 열단위로 돌면서 섬을 발견하면 다음 섬까지 거리를 구한다. 섬이 있는 부분을 기록해서 섬의 끝과 끝의 index로 거리를 계산한다. 2차원 ..

SWEA4008_숫자만들기 풀이 알고리즘 : BruteForce 처음엔 주어진 연산기호들로 순열을 만들어서 모든 경우에 대해 완전탐색을 하려하였으나 그렇게 되면 O(12!)가 되어 제한시간(50개에 대해 3초)를 초과할 것이라 생각되었다. 하지만 이 문제는 각 연산(최대 11개)이 결국 4가지 중 하나이고 이는 O(4^11)로 훨씬 적은 시간으로 연산을 해낼 수 있었다. 게다가 주어진 연산 갯수에 맞춰서 연산 갯수가 초과해서 연산을 수행할 수 없다. 이를 이용해서 각 단계의 연산을 골라서 최종적으로 연산 결과를 전역변수 maxRet과 minRet와 비교해서 저장하도록 하였다. 함수 calculate : 연산이 모두 결정되면 최종 연산결과를 리턴하는 함수 getResult : now부터 N-2 번째 연산기..

SWEA 1486 장훈이의 높은 선반 풀이 알고리즘 : BruteForce 사람들의 키 집합의 모든 부분집합의 키의 합을 구한다. 키의 합이 B 이상인 경우 중 최솟값을 출력한다. 함수 getSum : 구한 부분집합의 키의 합을 구해서 리턴하는 함수. getResult : 부분집합을 고르고 부분집합의 키의 합 중 B 이상이며 최소인 값을 리턴하는 함수 기저조건 : 부분집합의 크기가 지정한 크기(number)보다 크거나 같을 경우 부분집합의 합을 구해서 B이상이면 리턴한다. 코드 //! 2020.02.28 // TODO SWEA1486_장훈이의높은선반 #include using namespace std; const int MAX = 25; const int INF = 987654321; int T,N,B,..

SWEA1952 수영장 풀이1 알고리즘 : BruteForce 매 달 요금을 계산할 티켓수를 정해서 더한다. (일일권, 한달권, 세달권, 일년권 중에서) 일일권을 골랐다면 일수만큼 티켓 수를 더하고 나머지는 한개만 더한다. 다음달로 넘어갈 때 일일권, 한달권을 골랐다면 다음달로, 세달권,일년권을 골랐다면 세달,일년 만큼 다음달로 이동한다. 마지막 달 까지 티켓을 골랐다면 가격을 계산해서 리턴한다. 함수 getResult : idx번째 부터 11번째 달의 티켓을 결정하고 최소 가격을 리턴하는 함수 기저조건 : idx가 12번째 이상일 경우 최종 티켓 가격을 리턴한다. 코드1 #include using namespace std; const int INF = 987654321; int T; int price[..

https://www.acmicpc.net/problem/17136 풀이 10x10 종이를 탐색하면서 1이 칠해져 있는 부분을 찾는다. 찾는다면 1x1~5x5 색종이 중 붙일 수 있는 색종이를 붙여보고 1을 반복한다. 찾지 못한다면 다 붙인 경우이므로 총 붙인 갯수를 리턴한다. 1에서 가능한 갯수 중 최솟값을 출력한다. 함수 inRange : y,x를 받아서 종이 안에 포함되는지 확인하는 함수. min : n1,n2를 받아서 작은 값을 리턴하는 함수 checkSize : y,x,size를 받아서 y,x를 왼쪽 위 모서리로 하는 size x size 색종이를 붙일 수 있는지 확인하는 함수. fillMap : y,x,size,val을 받아서 y,x를 왼쪽 위 모서리로 하는 size x size 에 색종이를 ..

https://www.acmicpc.net/problem/2652 풀이 알고리즘 : DFS & 블록 체크 구현 Pseudo-Code 왼쪽 위 첫 점(1,1) 부터 오른쪽 아래(16,16) 마지막 점 까지 탐색한다. 'ㄷ'자 블록(1)을 만나면 DFS를 해서 1인 지점을 모두 check배열에서 True로 체크하고 왼쪽 맨 윗 점 P1과 오른쪽 맨 아래 점 P2을 만든다. P1(y1,x1)와 P2(y2,x2)로 만들어지는 사각형에서 뚫려있는 변의 원래길이 뚫린 길이와 변의 위치(상0 우1 하2 좌3)를 찾는다. 해당변의 시작부터 'ㅗ'자 모양의 블록을 끼워서 직사각형이 되는지 아닌지 체크한다. 뚫려있는 변의 길이와 u를 비교하고, 뚫린 길이와 y를 비교하여 다르다면 불가능 4-1..

https://www.acmicpc.net/problem/17281 안녕 풀이 알고리즘 BruteForce + Simulation 시간복잡도 50(이닝수) * 27(최악의 simulation : 3 아웃되는 동안 모든 타자가 타석에 서는 경우) * 8팩토리얼(타자 순서 정하는 모든 경우의 수) = 5500만 정도 함수 getResult : 타자 순서를 정하고 기저조건에서 점수를 얻어와 최대 점수를 반환하는 함수 playGame : 기저조건이 되었을 때 문제의 조건에 맞게 이닝별로 점수를 계산해서 반환하는 함수 movePlayer : 이닝별로 playGame에서 Simulation을 할 때 아웃이 아닌 경우에 1~3루, 홈 에 선수들을 옮기는 함수 코드 //! 2020.02.20 ~ 2020.02.21 /..

https://www.acmicpc.net/problem/16637 풀이 Algorithm BruteForce + Simulation inData : 초기 input 수식 check : 괄호를 넣을 때 앞에 위치하는 숫자의 index에 true값을 넣어둘 변수 numbers : inData 에서 숫자만 빼서 저장한 변수 calcs : inData 에서 수식만 빼서 저장한 변수 함수 changeArr : inData에서 numbers와 calcs를 만드는 함수 calculate : 수식, 숫자 2개를 받아서 수식에 맞는 연산을 한 후 결과를 반환하는 함수 getCalcRet : 괄호를 넣을 위치를 지정한 이후에 그에 맞게 처음부터 끝까지 연산한 값을 반환하는 함수 연산하는 방식은 다음과 같다. 첫번째 숫자..

2020.02.18 algospot / LIS 풀이 수열이 맨 왼쪽부터 하나씩 들어온다고 했을 때,다음 숫자가 들어왔을 때 그보다 작은 숫자들 중 최대인 녀석을 찾고 거기에 +1 한 값과 DP에 써져있는 값을 비교해서 큰 녀석을 DP에 update 한다. 이와 같은 풀이를 진행하면 C = 50, N = 500, 모든 수가 1~ 100000을 다 지나간다고 했을 때 대략 50 * 500 * 100000 정도의 시간복잡도가 될 거고 이는 25억이 되어 시간초과가 발생할 거라 생각했다. update하면서 가장 큰 최댓값을 기억해두고 마지막에 이를 출력한다. 해당 숫자를 맨 오른쪽 끝으로 하는 수열의 길이를 DP에 적어둔다. 1번의 알고리즘에서 들어온 숫자를 DP에 update하는 알고리즘은 동일하지만 들어온 ..