https://algospot.com/judge/problem/read/BRACKETS2 algospot.com :: BRACKETS2 Mismatched Brackets 문제 정보 문제 Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas ha algospot.com 각 괄호들의 짝을 맞춰준다. 스택을 이용해서 풀 수 있다. 중간에 짝이 안맞거나 스택에서 짝을 빼야할 시점에 스택이..
https://www.algospot.com/judge/problem/read/JOSEPHUS# algospot.com :: JOSEPHUS 조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하 www.algospot.com list를 이용해서 원형 연결 리스트를 구현한다. #include #include using namespace std; void josephus(int n, int k) { list survivors; for (int i = 1; i 2) { kill = survivors.erase(kill); if (kill == survivors.end()) ..
https://algospot.com/judge/problem/read/TRIPATHCNT algospot.com :: TRIPATHCNT 삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com count(x,y) = (x,y)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수 #include #include #include using namespace std; int n,triangle[100][100]; int cache[100][100],countCache[100][100]; int path(int x,int y) { i..
https://algospot.com/judge/problem/read/TILING2 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있 algospot.com tiling(n) = 2*n 크기의 사각형을 타일로 덮는 방법을 반환한다 tiling(n) = tiling(n-1) + tiling(n-2) #include #include const int MOD=1000000007; int cache[101]; int tiling(int n) { if(n
https://algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용 algospot.com classify(a,b) = n[a..b] 구간의 난이도를 반환한다 memorize(begin) = n[begin..]를 외우는 방법 중 난이도의 최소 합을 출력한다 memorize를 다음 1,2,3 중 최소값으로 정의할 수 있다. 1. 길이 3인 조각의 난이도 + 3글자 빼고 나머지 수열에 대한 최적해 2. 길이 4인 조각의 난이도 + 4글자 빼고 나머지 수열에 대한 ..
https://algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com jlis(indexA,indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이 #include #include #include using namespace std; typedef long long ll; const ll NEGINF=numeric_limits::min(); int n,m,A[100],B[100]..
https://algospot.com/judge/problem/read/LIS# algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. algospot.com lis(start) = s[start]에서 시작하는 부분 증가 수열 중 최대의 길이 #include #include #include using namespace std; int n,cache[500],s[500]; int lis(int start) { int &ret=cache[start]; if(ret..
https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 algospot.com path(x,y) = (x,y)에서 시작해서 맨 아래줄까지 내려가는 부분 경로의 최대 값을 반환한다 #include #include #include using namespace std; int n,triangle[100][100]; int cache[100][100]; int path(int x,int y) { if(x..
https://algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 algospot.com cache[i][j] : W[i...]와 S[j...]가 대응하면 1, 아니면 0, 아직 계산되지 않았으면 -1 matchMemoized(w,s) : W[w...]와 S[s...]가 대응하는지 확인한다 와일드카드의 문자가 ?이거나 와일드카드와 파일이름의 문자가 일치하면 두 문자열 모두 인덱스 하나 증가시켜주면 된다. 와일드카드의 끝까지 왔다면 파일이름도 끝..
https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com go(x,y) : (x,y)에서 도착점(n-1,n-1)까지 도달할 수 있으면 1, 아니면 0을 반환한다. cache를 잡아서 중복해서 함수 호출이 일어나지 않도록 한다. #include #include int t,n,map[100][100],cache[100][100]; int go(int x,int y) { if(x>=n || y>=n) return 0; i..