블로그 언저리인 무언가

문제 : 2166 다각형의 면적 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2차원 평면상의 점으로 이루어진 다각형의 면적을 출력하는 문제이다. N각형을 (N-2)개의 삼각형으로 쪼개서 CCW를 이용해 각각의 넓이를 구한 뒤 합쳐주면 된다. 다 풀어놓고 틀려서 이유를 몰랐는데 백준 질문글을 보고 절댓값 처리를 매번 해주지 않고 마지막에 한 번만 하도록 바꾸니 맞았다. 매번 절댓값을 씌웠을 때 틀리는 이유는 잘 모르겠다... Code #include #define ll long long using namespace std; typed..

문제 : 9019 DSLR 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 두 수가 주어졌을 때 어떤 행동을 통해 첫 번째 수를 두 번째 수로 바꾸는 최소 횟수와 그 경로를 출력하는 문제이다. BFS를 이용해 최소 횟수를 구하면서, 가는 경로를 저장하는 문자열 배열도 만들어 추가로 저장해주면 된다. 나 같은 경우에는 그냥 pair를 활용해 최소 횟수와 경로를 저장하는 배열을 한데 묶어 저장했다. Code #include #define ll long long using namespace std;..

문제 : 5525 IOIOI 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net x가 주어졌을 때, x+1개의 I와 x개의 O가 교대하는 문자열의 개수를 찾아 출력하는 문제이다. 그냥 중첩 반복문을 사용해 풀게 되면 O(N^2)으로 시간 초과가 나게 되므로 시간을 O(N)으로 줄여야 한다. 가장 길게 교대하는 문자열의 크기가 y이라고 할 때, 안에 속하는 부분 문자열의 개수는 y-x+1 임을 활용하여 풀면 된다. Code #include #define ll long long using namespace std; int main(){ ios..

문제 : 1780 종이의 개수 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 종이가 모두 같은 숫자로 이루어졌는지 확인하고 만약 다른 숫자가 포함된다면 종이를 9 등분하는 것을 반복하는 문제이다. 분할 정복을 이용해 재귀 함수 코드를 작성해 시작 좌표와 가로세로 길이를 정해준 후 반복하면 된다. Code #include #define ll long long using namespace std; ll N, arr[2500][2500], ans[3]; void f(ll x, ll y, ll size)..

문제 : 1213 팰린드롬 만들기

문제 : 1531 투명 1531번: 투명 첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌� www.acmicpc.net 100*100 크기의 그림에서 가려진 그림의 개수를 구하는 문제이다. 배열의 크기가 크지 않기 때문에 통째로 저장한 후 값이 M이상인 곳을 체크해 출력하면 된다. Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll N, M, arr[105][105], ans=0; fill(&arr[0]..

문제 : 9715 면적 구하기 9715번: 면적 구하기 아래 다면체는 1x1x1 정육면체로 만들어져있다. 이 문제에서는 블록이 땅에 닿지 않고 공중에 떠있는 경우는 고려하지않는다(각 칸에는 한개 이상의 정육면체가 차곡차곡 쌓아 올려져있다). 이런 www.acmicpc.net 격자 공간에 네모난 박스가 쌓여있는 모양이 주어지고 겉넓이의 면적을 구해 출력하는 문제이다. 모든 위치를 체크하면서 박스가 존재한다면 위, 아래면이 있으므로 2씩 더하고 각 박스의 층마다 사방을 확인해 비어있거나 높이가 낮다면 1씩 더하게 만들었다. Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0);..