너와 나의 스토리

문제: https://www.acmicpc.net/problem/1541 문제 풀이: +, - 기호만 사용 - 가 나오면 그 뒤는 전부 -|값|으로 연산해주면 된다. -> 괄호로 묶을 수 있기 때문에 소스 코드: 더보기 #include #include #include #include using namespace std; string s, num; int res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); string s; cin >> s; bool flag = true; for (int i = 0; i < s.size(); i++) { if (s[i] == '+' || s[i]=='-') { if(flag) res +..

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN#none 문제 풀이: 1. 0이 아닌 직사각형들 찾기 2. 행렬들을 곱셈 가능한 순서로 나열 -> "1259. [S/W 문제해결 응용] 7일차 - 금속막대" 문제와 동일한 풀이법 -> 이 블로그의 풀이를 참고하였습니다. 3. 연쇄 행렬 최소 곰셈 알고리즘 사용 -> 2019/11/22 - [알고리즘/기타] - [BOJ] 11049 행렬 곱셈 순서 소스 코드: #include #include #include #define inf 987654321 using namespace std; typedef pair P; vector v; in..

문제: https://www.acmicpc.net/problem/11049 문제 풀이: 연쇄 행렬 최소 곱셈 공식 - DP 소스 코드: #include #include #include #define inf (1 n; for (int i = 0; i > a >> b; d[i] = a; if (i == n - 1) d[i + 1] = b; } for (int diagonal =0; diagonal < n; diagonal++) { for (int i = 1; i

문제: https://www.acmicpc.net/problem/1687 문제 풀이: '히스토그램에서 가장 큰 직사각형' 문제에서 스택을 사용한 풀이법을 이용하면 된다. - func()함수: 현재 위치에서 위로 0의 개수(막대의 높이)를 기록 [현재 위치에서 막대의 높이=자신의 위에 저장된 값+1]로 저장하면 된다. - 모든 높이에 대해 func2()함수를 돌려 최대 직사각형 크기를 찾는다 func2() 함수는 '히스토그램에서 가장 큰 직사각형 문제 풀이와 동일하다 - 전체에서 가장 큰 크기를 찾을 것이기 때문에 ans는 맨 처음 0으로 초기화해주는 것을 제외하고는 초기화하지 않는다. 소스 코드: #include using namespace std; typedef long long ll; int n, m..

문제: https://www.acmicpc.net/problem/13560 문제 풀이: 4명이 경기를 한다고 가정해보자. (A, B, C, D) A가 B,C,D를 모두 이긴다면 승점 3 B가 C,D를 이긴다면 승점 2 C가 D를 이긴다면 승점 1 D는 모두에게 졌으므로 승점 0 총 승점은 6 만약 A가 B,C만 이기면 승점 2 B가 C,D 이기면 승점 2 C가 D 이기면 승점 1 D가 A 이기면 승점 1 총 승점은 6 즉, 누가 누구를 이기든 총 승점은 (n-1)*n/2가 된다. * 총 승점이 (n-1)*n/2이 아니면 항상 유효하지 않지만, 총 승점이 (n-1)*n/2이라고 해서 항상 유효한 것은 아니다. 입력 받은 각 팀의 점수를 오름차순으로 정렬했을 때, 2명이 경기 했다면 최소 승점 1이 있어야 ..

문제: https://www.acmicpc.net/problem/16287 문제 풀이: 풀이 1: O($N^{2}$)으로 값 2개의 합을 벡터에 저장한다. 이때, 2개의 합은 최대 400000이므로 크기만큼 미리 벡터를 선언해줄 수 있다. 2개를 합친 값이 동일한 것이 여러개 있을 수 있으므로 각 값의 위치를 저장해준다. 2~400000(2개 합쳐서 나올 수 있는 값)들을 다 보며, 지금 값이 존재하고 (총 무게-현재 2개 합)도 존재할 때, (i,j) 서로 다른 두 쌍을 가지고 있다면 yes를 출력하고 종료한다. 풀이2: 풀이1처럼 풀면 굉장히 오래걸린다. 각 두 쌍에 겹치는게 있는지 확인하는 과정이 오래 걸린거였는데 이렇게 해결할 수 있다. 이중 포문 i, j로 돌려서 2개 합을 구할 때, dp[두개..

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWtInr3auH0DFASy 문제 풀이: 가장 작은 값, 큰 값 구해서 곱해주면 된다. 소스 코드: #include using namespace std; int tc, n; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> tc; for(int z=1;z> n; int small= 1000001, big = 2; for (int i = 0; i > a; small = small > a ? a : small; big = big ..

문제: https://www.acmicpc.net/problem/9934 문제 풀이: 위에서부터 왼쪽에서 오른쪽으로 1번부터 순서를 매긴다고 하자. 깊이가 k일 때, 마지막 레벨의 번호는 $2^{k-1}$≤N≤$2^{k}-1$이다. l: $2^{k-1}$ r: $2^{k}-1$ pos: 1 (도착 순서) 이라고 하자. 1. 왼쪽 노드를 방문 안했고 현재 l보다 작다면(아직 마지막 층이 아니라면) -> 왼쪽 노드로 이동 2. 왼쪽 노드를 방문 했고 현재 자신의 위치에서 방문한 적이 없으면 -> 입력 받은 순서대로 트리의 해당 위치에 값을 넣어준다. 3. 현재 위치를 방문했고, 오른쪽 노드는 방문 하지 않았는데 현재 l보다 작다면 -> 오른쪽 노드로 이동 소스 코드: int h,l,r,arr[1026],re..