풀이 n번째에 붙게되는 정삼각형의 한 변의 길이는 n-1번째의 최대 길이이다. 길이는 6각형의 각 변의 길이로 경우의 수를 나눌 수 있다고 생각하였다. 0번째는 0, 1번째는 1을 기록해두고 1번째 6가지 변에 0,1,0,1,0,1을 담는다 (한개의 정삼각형이 있는 경우 6가지 변의 길이.) n번째 경우의 수에 대한 메모를 확인한다. 메모가 되어있지 않다면 n-1번째 경우의 수가 메모가 되어있는지 확인한다. 메모가 되어있지 않다면 재귀함수를 이용해 거기 먼저 메모하도록 한다. 메모가 되어있다면 n-1번째 6가지 변이 기록되어 있다는 것을 의미하므로 그 중 가장 긴 변을 찾아 n번째에 기록하고 n번째 6가지 변을 update한다. 메모가 되어 있다면 메모를 리턴한다. (1번째는 1이 기록되어있고 6가지 변..

풀이 방문여부를 DP로 이용하는 BFS SWEA의 보급로 문제의 풀이와 약간 유사하면서 다른 점이 있다 https://tbtb7-sw.tistory.com/95 탐색할 때 다음 지점을 탐색할 때 경우의 수를 나눠야 했고 비용을 기록하는 방식이 약간 달랐다. 첫 지점을 시작으로 주변 점들을 탐색한다. loop가 한번 돌 때 이동한 거리가 같은 경우의 수가 큐에 모두 담겨있고 각 경우를 모두 확인하고 루프를 계속한다.(한턴한턴 진행하는 것 처럼) 현재까지 이동한 거리를 cnt를 이용하여 기억하고 있으며 주변 점을 탐색했을 시 이동 거리를 DP 배열에 기록해둔다. 큐에 있는 탐색할 점의 4방향을 확인한다. 벽을 부순 적이 있을 때 벽이 없는 곳만 방문 가능하다. 벽을 부순 적이 없을 때 벽이 있든 없든 방문 ..

풀이1 첫번째 시도는 DFS와 백트래킹이었다 물론, 입력의 최대가 100 x 100 이므로 제한시간 1초(1억번의 연산) 을 훨씬 넘어설 거라 생각했다. inRange : 범위 안인지 체크하는 함수 isEnd : 마지막 지점인지 체크하는 함수 getResult : DFS, 백트래킹을 이용해서 마지막 지점에 도착했을 때(기저조건) 그때까지 비용과 현재까지의 최솟값과 비교해서 result를 update 하는 함수 역시나 시간초과 코드1 #! Backtracking Algorithm import sys sys.stdin = open('input.txt', 'r') sys.setrecursionlimit(10**6) T = int(input()) dx = [1,0,-1,0] dy =..

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..