너와 나의 스토리

문제: 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/10538 문제 풀이: * 이 분의 풀이를 참고하여 풀었습니다. 작은 그림의 높이: q, 너비: w 큰 그림의 높이: e, 너비: r Part 1. 작은 그림 작은 그림의 행을 하나의 단어로 취급 즉 작은 그림은 q개의 단어를 가짐 각 단어를 map에 넣어 번호를 매긴다 -> 중복되면 같은 번호를 가지는 것 이때 저는 map을 구현하여 값이 저장된 위치를 단어의 번호로 사용하였습니다. map에 존재하지 않는 단어이다 -> trie에 insert -> trie 속 단어의 끝에 해당 단어의 번호를 저장해준다. (terminal=num) * map에 이미 존재하는 단어를 넣어봐야 중복되서 의미 없음 Part 2. 큰 그림 큰 그림의 한 줄씩 보면..

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do 문제 풀이: 우리는 header와 main 함수 부분을 제외한 부분을 라이브러리를 사용하지 않고 채우면 된다. main 코드를 보면 한 블록에서 높이는 다음과 같이 나올 수 있다. base는 1~6까지가 나올 수 있고, 거기에 플러스로 0~2가 더해진 수가 나올 수 있으므로 높이는 1~8가 나올 수 있다. 높이가 최대 8밖에 안되므로 long long형 16자리로 표현할 수 있다. 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 => 1111222233334444 이런식으로 블록의 모양을 state라고 하자. hash_table을 만들어 각 블록의 state를 저장하였다...

문제: https://www.acmicpc.net/problem/13567 문제 풀이: int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; 0: 상 1: 우 2: 하 3: 좌 로 설정해 놓고 좌표를 가리키는 변수 하나, (x,y) 값을 표시하는 변수 하나 만들고 기록하면서 움직이면 됨 소스 코드: #include #include #include #include #include #include using namespace std; typedef pair P; int n, m; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int dir; P pos; bool move(int dist) { pos.first += dx[d..

문제: https://www.acmicpc.net/problem/13565 문제 풀이: 맨 윗줄에서 0인 위치를 큐에 넣어놓고 시작해서 마지막 줄에 도달하는지만 보면 된다. 소스 코드: #include #include #include #include #include using namespace std; typedef pair P; int n, m; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1, -1, 0, 0 }; char arr[1002][1002]; bool visit[1002][1002]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = ..

문제: https://www.acmicpc.net/problem/13561 문제 풀이: 투 포인터를 이용하여 문제를 풀 수 있다. O(n)으로 문제를 풀 수 있다. l~r 사이에 포함되는 타입들을 1씩 증가해서 표시한다. -> kind[v[r].second]++; 다 포함됬으면, 제일 먼 두 타입의 위치의 합 나누기 2로 최적의 위치를 구한 후, l++ 시켜가면서 이렇게 범위 줄여도 다 포함되는지 확인한다. 4 7 -6 2 -5 1 -3 1 -2 2 0 3 1 2 2 4 이런 케이스가 있을 수 있기 때문. * 주의: (l+r)/2로 위치를 찾을 때, 두 값의 합이 음수이고 2로 나누어 떨어지지 않는다면 최적의 위치보다 큰 값이 선택된다. 하지만 우리는 최대 거리가 같을 때, 더 작은 값을 출력 해줘야 하..

문제: 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/5719 문제 풀이: 다익스트라 한 번 돌리고 뒤에서부터 최단 경로인 것들 다 지운 다음에 다익스트라 다시 돌림 소스코드: #include #include #include #include #include #define inf 5000001 using namespace std; typedef pair P; int n, m,dist[501],adj[501][501]; bool visit[501]; void di(int start,int end) { fill(dist, dist + n+1, inf); priority_queue pq; memset(visit, false, sizeof(visit)); dist[start] = 0; pq.push({..