티스토리

henry's PS diary

검색하기

블로그 홈

henry's PS diary

henry121407.tistory.com/m

henry1214 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

9/7 Problem Solving 1099 알 수 없는 문장 (G3) dp[i] = i번째 문자까지 만들 수 있는 최소 비용 http://boj.kr/2f180cfc6e6f445b98191f366c8a98a6 1082 방 번호 (G3) dp[i] = i원을 사용해서 만들 수 있는 가장 큰 방 번호 http://boj.kr/a6889080f221488e92ca74fea010ec92 2248 이진수 찾기 (G3) 이항계수의 성질을 이용해서 범위 안의 combination 값들을 미리 계산해준다. 그리고 가장 높은 자리부터 내려가면서 i-1개 자리에서 L개 이하의 1개 배치될 수 있는 모든 경우의 수보다 현재 I가 크다면 현재 자리에 1을 넣는다. 그렇지 않다면 0을 넣는다. 이런식으로 I번째 이진수를 구할 수 있다. http://boj.. 공감수 4 댓글수 1 2024. 9. 7.
9/6 Problem Solving 11657 타임머신 (G4) 벨만포드 알고리즘을 수행한다. 거리 배열을 구할 때 데이터 타입 범위에 주의하자. long long을 사용해야 한다. http://boj.kr/5de133d5fa8140b399f4a77308c66fc4 5052 전화번호 목록 (G4) 전화번호들을 사전순으로 정렬한 다음에 인접한 번호끼리 비교한다. 만약에 앞의 번호가 뒤의 번호의 접두어가 된다면 일관성이 없다고 판단할 수 있다. http://boj.kr/42a1be5b39594611bbae780a7ebc36fd 14852 타일 채우기 3 (G4) dp[n] = 2*n 크기의 벽을 2*1,1*2,1*1 크기의 타일로 채우는 경우의 수 그림을 그려보면서 타일의 끝부분에 주목하면 점화식을 유도할 수 있다.dp[n] = 2*dp[.. 공감수 1 댓글수 0 2024. 9. 6.
9/5 Problem Solving 12996 Acka (G3) dp[i][j][k] = dotorya가 a곡, kesakiyo가 b곡, hongjun7이 c곡 불렀을 때 앨범을 만들 수 있는 방법의 수 http://boj.kr/bdc634c727a04427a168e6dc58fe44b7 14505 팰린드롬 개수 구하기 (Small) (G3) dp[i][j] = s[i:j+1]의 부분 수열 중 팰린드롬의 개수 http://boj.kr/09b6e26c69a34dc187a26a8b45a23944 1823 수확 (G3) dp[i][j] = v[i:j+1]까지 벼가 남았을 때 얻을 수 있는 최대 이익 http://boj.kr/01f888a3ed214dbe9295b5d0467a6d1b 5015 ls (G3) dp[i][j] = 패턴의 처음 i개.. 공감수 0 댓글수 0 2024. 9. 5.
9/4 Problem Solving 1106 호텔 (G4) dp[i] = 고객 i명을 유치하기 위해 필요한 최소 비용 http://boj.kr/eda56c043fe04b94863a76278da6f9a4 2624 동전 바꿔주기 (G4) dp[i] = i원을 만들 수 있는 방법의 수 http://boj.kr/0c30a754956b47ba8af519f7861feffb 12869 뮤탈리스크 (G4) dp[a][b][c] = SCV 3개의 체력이 각각 a,b,c일 때, SCV들을 모두 파괴하는 데 필요한 최소 공격 횟수 SCV의 체력이 최대 60이므로 상태 공간을 60*60*60으로 설정한다. BFS를 돌리면서 최소 공격 횟수를 dp 테이블에 기록한다. 최종 정답은 모든 SCV가 파괴된 상태인 dp[0][0][0]이다. http://boj.kr.. 공감수 2 댓글수 0 2024. 9. 4.
9/3 Problem Solving 8913 문자열 뽑기 (G3) 문자열의 길이가 최대 25이므로 모든 경우에 대해서 재귀적으로 각 그룹들을 제거하면서 빈 문자열이 되는지 확인하면 된다. http://boj.kr/d0f8be3020c64594a794f24b69baf0d6 11062 카드 게임 (G3) dp[i][j] = i에서 j까지의 카드들이 남아 있을 때, 근우가 가져갈 수 있는 최대 점수 근우가 카드를 가져갈 때, 가장 왼쪽 카드 또는 가장 오른쪽 카드를 가져갈 수 있다. 이 때 명우가 최적의 선택을 했을 경우 남아있는 카드들 중에서 명우가 얻는 점수를 뺀 값을 근우의 점수로 기록한다. http://boj.kr/9d3a5872aab64fe6b3ac294b7ac8d865 14428 수열과 쿼리 16 (G1) 세그먼트 트리로 구간의 .. 공감수 3 댓글수 0 2024. 9. 3.
9/2 Problem Solving 1949 우수 마을 (G2) dp[node][0] = 해당 노드를 선택하지 않았을 때, 자식 노드에서 얻을 수 있는 최대 주민 수dp[node][1] = 해당 노드를 선택했을 때, 자식 노드에서 얻을 수 있는 최대 주민수 위와 같이 정의하고 DFS를 이용해서 트리에서의 DP 테이블을 계산해준다. 최종 정답은 루트 노드에서 선택한 경우와 선택하지 않은 경우 중 최댓값이다. http://boj.kr/ff3f639352ba41309973b3102f4e1ff1 14267 회사 문화 1 (G4) 상사에서 부하로 이어지는 단방향 트리를 만든다. 이후 칭찬에 대한 정보가 주어질때마다 매번 DFS를 돌리는것이 아니라 칭찬의 시작점에만 기록을 해놓는다. 그리고 루트에서부터 DFS를 한번만 돌리면서 칭찬을 누적해서 더해.. 공감수 2 댓글수 0 2024. 9. 2.
9/1 Problem Solving 28706 럭키 세븐 (G5) 선택지를 모두 고른 이후 결과로 나온 K가 7의 배수가 되도록 할 수 있는지 판단하면 되므로 매 턴마다 modular 7한 결과값만 들고 다니면 된다. set으로 결과값들을 관리했다. http://boj.kr/6aed488c749c43d1920d15d2cf259ef5 8901 화학 제품 (G5) AB,BC,CA 세 가지 조합을 만들 수 있는 모든 경우를 확인한다. http://boj.kr/7970c2bd2c654a45bcb24575041fe6aa 17025 Icy Perimeter (G5) 가장 큰 컴포넌트를 찾는다. 그러한 컴포넌트가 여러 개 있으면 둘레가 작은 것이 답이다. DFS/BFS 중 아무거나 이용하면 된다. http://boj.kr/ad36b1b6f96444.. 공감수 1 댓글수 0 2024. 9. 1.
8/31 Problem Solving 2482 색상환 (G3) d[i][j] = i개의 색 중에서 j개의 색을 인접하지 않게 선택하는 경우의 수 (초기 조건 설정)d[i][1] = i : i개의 색 중에서 1개의 색을 선택하는 경우는 i가지가 존재한다.d[i][0] = 1 : i개의 색 중에서 0개의 색을 선택하는 경우는 1가지이다. (점화식)d[i][j] = d[i-2][j-1] + d[i-1][j]d[i][j]를 구할 때, i번째 색을 선택하는 경우에는 i-1번째 색은 선택할 수 없으므로 i-2개의 색에서 j-1개의 색을 선택하는 경우와 같다. i번째 색을 선택하지 않은 경우에는 i-1개의 색에서 j개의 색을 선택하는 경우와 같다. (최종 정답)d[n-3][k-1] + d[n-1][k]색깔들이 원형으로 있으므로 첫 번째 색과 마지막 색이.. 공감수 2 댓글수 0 2024. 8. 31.
8/30 Problem Solving 14466 소가 길을 건너간 이유 6 (G3) 모든 소들의 쌍에 대해서 다리를 건너지 않고 인접한 칸으로 이동해서 도착할 수 있는지 확인해주면 된다. BFS/DFS 중 아무거나 이용해도 된다. http://boj.kr/95aadfb791fa4472a470b95b2aa37c5c 14452 Cow Dance Show (G4) 무대 크기 K가 될 수 있는 범위 안에서 답을 가정하고 parametric search를 한다. min heap을 이용해서 현재 K가 가능한지 판단한다. 초기에는 무대에 K마리의 소가 동시에 올라가고 그 후로는 가장 먼저 춤을 끝낸 소가 무대에서 내려가는 시간에 다음 소가 무대에 오르게 된다. 공연이 Tmax 내에 끝난다면 더 작은 K값을 탐색하고 그렇지 않다면 더 큰 K값을 탐색한다.. 공감수 2 댓글수 0 2024. 8. 30.
8/29 Problem Solving 16500 문자열 판별 (G5) dp[i]를 문자열 S의 처음부터 i번째 문자까지의 부분 문자열을 만들 수 있는지를 나타내는 boolean 값으로 정의한다. 초기값으로 dp[0]은 true이다. 이는 빈 문자열을 만들 수 있다는 의미이다. dp[i]를 계산하기 위해 j를 0부터 j-1까지 순회하면서 dp[j]가 true이고 s[j:i]가 단어 목록 A에 포함되는지 확인한다. 만약 그렇다면 dp[i]를 true로 설정한다. 이와 같이 O(N^2)에 테이블을 채울 수 있다. 최종 정답은 dp[n]이다. http://boj.kr/19f69b00d92f4ed2a4162ba4fd28893c 3987 보이저 1호 (G5) 탐사선의 위치에서 위,아래,오른쪽,왼쪽 4방향으로 모두 시그널을 보내본다. 시뮬레이션을 잘 .. 공감수 2 댓글수 0 2024. 8. 29.
8/28 Problem Solving 14172 Moocast (G5) 모든 소들의 쌍에 대해서 a->b로 가는 거리가 power 안에 들어오면 간선으로 이어준다. 거리를 계산할때 제곱끼리 비교해서 실수 연산을 최대한 피해준다. 그리고 모든 점에 대해서 BFS로 도달할 수 있는 소들의 최댓값을 구해주면 된다. http://boj.kr/a841ac2eadbe418ba6030ddad02d28e9 14464 소가 길을 건너간 이유 4 (G1) 소들을 Bj를 기준으로, Bj가 같다면 Aj를 기준으로 정렬한다. 닭은 Ti를 기준으로 오름차순 정렬한다. 그리고 소들을 한 마리씩 보면서 그리디하게 Ti가 가장 작은 닭에게 매칭시켜주면 된다. http://boj.kr/e5b7f5e2de2f400e874a91d1cd9820d0 2109 순회강연 (G3).. 공감수 2 댓글수 0 2024. 8. 28.
8/27 Problem Solving 3013 부분 수열의 중앙값 (G3) 주어진 수열에서 중앙값이 B인 부분 수열의 개수를 계산해야한다. B의 위치를 기준으로 이전의 원소들을 보면서 psum을 B보다 크면 +1, B보다 작으면 -1해주면서 map에 특정 누적합 발생 빈도를 기록한다. 그리고 B의 위치부터 오른쪽으로 보면서 다시 psum을 계산하면서 -psum이 왼쪽 부분에서 발생했는지 확인해서 해당 부분 수열의 개수를 답에 세주면 된다. http://boj.kr/96cf2289845049e38029a2fbfe662fd5 1865 웜홀 (G3) 벨만 포드 알고리즘을 적용하여 음의 사이클이 존재하는지 여부를 판단하는 고전적인 문제이다. 그래프의 컴포넌트가 하나가 아닐 수도 있으므로 편의상 가상의 정점 0을 추가하여 실제 모든 정점을 이어줬다.. 공감수 3 댓글수 0 2024. 8. 27.
8/26 Problem Solving 15927 회문은 회문아니야!! (G5) 문자열 s가 주어졌을때 길이를 n이라고 하자. s 자체가 팰린드롬이 아니라면 n을 출력해주면 된다. s가 팰린드롬이라면 만약에 전체가 똑같은 글자로 이루어진 팰린드롬이면 모든 부분문자열이 팰린드롬이므로 -1이 답이다. 그렇지 않다면 맨 앞이나 뒤에서 하나만 빼주면 팰린드롬이 아니게 된다. 즉 n-1이 답이다. http://boj.kr/3cb717aee0e141adb4e5edd5b5b46afb 14370 전화번호 수수께끼 (Large) (G4) 각 숫자에 대응하는 영어 단어에서 고유한 문자를 찾는다. 0 : ZERO (Z)2 : TWO (W)4 : FOUR (U)6 : SIX (X)8 : EIGHT (G)1 : ONE (O) - O는 0에서 쓰였으므로 0을 먼저 .. 공감수 7 댓글수 2 2024. 8. 26.
8/25 Problem Solving 15961 회전 초밥 (G4) 슬라이딩 윈도우로 고정된 구간을 연속적으로 보면서 초밥 가짓수의 최댓값을 구한다. 쿠폰 사용 여부를 따로 변수로 둬서 누적해서 세는 경우가 없도록 했다. http://boj.kr/07bfe0b8abf94fc99b0e67dd9e6f4a22 9011 순서 (G5) R를 이용해서 S를 구하려면 R의 뒤에서부터 거꾸로 봐야지 원소들을 하나로 정할 수 있다. check 배열을 따로 둬서 현재 위치의 앞에 r[i]가 check 안되어있으면 s[i]를 정할 수 있다. 끝까지 봤는데도 아직 자리를 못찾으면 IMPOSSIBLE를 출력해준다. http://boj.kr/c3d6b307fa5640e49d4b74a223c3f1cf 16985 Maaaaaaaaaze (G2) 판 하나당 4가지 경.. 공감수 4 댓글수 0 2024. 8. 25.
8/24 Problem Solving 9470 Strahler 순서 (G3) 위상 정렬을 하면 되는데 조건이 붙어있다. 노드로 들어오는 강의 순서 중 가장 큰 값을 cnt 배열을 두고 관리했다. 이 부분에서 구현이 조금 엉켜서 애먹었다. http://boj.kr/bd1acde263c04d71bcdb47d6187cbce5 15483 최소 편집 (G3) d[i][j] = 문자열 a의 첫 i개의 문자를 문자열 b의 첫 j개의 문자로 만드는데 필요한 최소 편집 횟수 만약 a의 i번째 문자와 b의 j번째 문자가 같다면 d[i][j] = d[i-1][j-1]이다. 문자가 다르다면 삽입, 삭제, 교체 세 가지 경우 중에서 최소값을 선택해서 테이블을 채운다. http://boj.kr/c148fea9541c466d821362fc4404ad81 2655 .. 공감수 36 댓글수 20 2024. 8. 24.
8/23 Problem Solving 2623 음악프로그램 (G3) 각 PD들의 가수 출연 순서에 따라 단방향 그래프를 만든다. 그 다음에 Topological Sort를 해줘서 전체 출연 순서를 정한다. Directed Acyclic Graph를 이루면 전체 가수의 수만큼 정확히 출력이 될것이고 아니면 순서 정하는 것이 불가능하므로 0을 출력한다. http://boj.kr/09f1e0b6e82c457e89e3a05fb6143178 4386 별자리 만들기 (G3) 각 별들의 좌표를 정점으로 생각하고 좌표들 간의 거리를 간선으로 생각하면 그래프를 구성할 수 있다. 그리고 Minimum Spanning Tree를 구성하면 별자리를 만드는 최소 비용을 구할 수 있다. http://boj.kr/a587be0a5a53456583384ae27fbc0.. 공감수 3 댓글수 0 2024. 8. 23.
8/22 Problem Solving 2825 수업시간에 교수님 몰래 교실을 나간 상근이 (G2) 비트 마스크로 0~9 사이의 숫자가 포함되어 있는지 여부를 상태로 표현해서 세준다. 쌍의 개수를 세줄 때 자기자신끼리의 쌍과 중복되는 쌍은 제거해야한다. http://boj.kr/065bfe2aa12a4a85abb60aed0ed3d74a 17497 계산기 (G2) 처음에는 BFS로 생각했는데 경우의 수가 최대 4^99가 되서 불가능하다. 연산이 전부 2와 연관이 있는것에 주목하자. 2를 더하는 것은 1번째 비트에 1를 추가하는 것과 같고 빼는 것도 마찬가지이다. 곱하기는 left shift, 나누기는 right shift와 같다. 우리가 구해야 하는 것은 0에서 N까지 가는 방법인데 N에서 0으로 만드는 방법을 생각해보자. 1. 0번째 비트에.. 공감수 48 댓글수 23 2024. 8. 22.
8/21 Problem Solving 오늘부터 연말까지 골드 문제 중에 랜덤으로 최소 5문제 이상씩 풀어보려고 한다. 골랜디가 80% 이상 방어되는게 목표다. 꾸준히 해보자.. 1477 휴게소 세우기 (G4) 처음에는 priority queue를 이용해서 greedy하게 m번에 걸쳐서 제일 큰 구간을 반씩 자르면 될것이라고 생각했다. 근데 생각해보니까 한 구간을 여러번 분할하는게 답이 되는 경우도 있어서 이 접근은 틀렸다. 구간의 최댓값의 최솟값이 될 수 있는 범위를 후보로 놓고 parametric search를 해서 답을 찾으면 된다. http://boj.kr/4481a6d19d05480db5e86a48da136770 2473 세 용액 (G3) 일단 정렬한 후에 모든 용액에 대해 하나의 용액을 fix하고 나머지 두 개의 용액에 대해서 .. 공감수 36 댓글수 17 2024. 8. 21.
5573 산책 https://www.acmicpc.net/problem/5573 5573번: 산책 첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107) 둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은 www.acmicpc.net d[i][j] = n-1번 산책한 후 교차로 (i,j)의 방문 횟수 i) d[i][j] = 짝수이면 초기 방향 상태가 그대로 유지된다 ii) d[i][j] = 홀수이면 초기 방향 상태와 방향이 다르다 위의 dp 정의를 통해 점화식을 찾아보자. 시작점은 무조건 지나므로 초기값 d[1][1] = n-1이다. 오른쪽, 아래쪽으로 가는 경우인 d[i][j+1],d[i+1].. 공감수 0 댓글수 0 2023. 11. 22.
DP + 필수 문제 풀 것들 1562 계단 수 (G1) 1509 팰린드롬 분할 (G1) 2618 경찰차 (P5) 2482 색상환 (G4) 11062 카드 게임 (G3) 10217 KCM Travel (G1) 1102 발전소 (G1) 11266 단절점 (P5) 11657 타임머신 (G4) 3955 캔디 분배 (P5) 2162 선분 그룹 (P5) 1708 볼록 껍질 (P5) 3190 뱀 (G5) 15684 사다리 조작 (G4) 5373 큐빙 (P5) 16235 나무 재테크 (G4) 2174 로봇 시뮬레이션 (G4) 1726 로봇 (G3) 9328 열쇠 (G1) 1405 미친 로봇 (G5) 13226 Divisors Again (S4) 1671 상어의 저녁식사 (P3) 2473 세 용액 (G4) 2188 축사 배정 (P4) 11375 열.. 공감수 0 댓글수 0 2021. 12. 24.
BRACKETS2 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 각 괄호들의 짝을 맞춰준다. 스택을 이용해서 풀 수 있다. 중간에 짝이 안맞거나 스택에서 짝을 빼야할 시점에 스택이.. 공감수 0 댓글수 0 2021. 6. 27.
JOSEPHUS 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()) .. 공감수 0 댓글수 0 2021. 6. 23.
TRIPATHCNT 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.. 공감수 0 댓글수 0 2021. 6. 21.
TILING2 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 공감수 0 댓글수 0 2021. 6. 21.
PI 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글자 빼고 나머지 수열에 대한 .. 공감수 0 댓글수 0 2021. 6. 21.
JLIS 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].. 공감수 0 댓글수 0 2021. 6. 21.
LIS 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.. 공감수 0 댓글수 0 2021. 6. 21.
TRIANGLEPATH 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.. 공감수 0 댓글수 0 2021. 6. 21.
WILDCARD 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...]가 대응하는지 확인한다 와일드카드의 문자가 ?이거나 와일드카드와 파일이름의 문자가 일치하면 두 문자열 모두 인덱스 하나 증가시켜주면 된다. 와일드카드의 끝까지 왔다면 파일이름도 끝.. 공감수 0 댓글수 0 2021. 6. 20.
JUMPGAME 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.. 공감수 0 댓글수 0 2021. 6. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.