블로그 언저리인 무언가

문제 : 1668 트로피 진열 1668번: 트로피 진열 민식이는 “오민식”이라는 팀이름으로 수없이 많은 로봇대회를 우승했다. 따라서 민식이의 집에는 트로피가 많다. 민식이는 트로피를 어떤 선반 위에 올려놨다. 이 선반은 민식이의 방문을 열 www.acmicpc.net 배열의 앞과 뒤에서 눈에 보이는 트로피 개수를 세는 문제이다. 순차적으로 높이를 체크하면서 지금까지의 최고 높이보다 높다면 최고 높이를 갱신하고 보이는 트로피의 개수를 늘려주면 된다. Code #include #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll N, arr[55]={0}, ans[2]={0,}, chk[2]={..

문제 : 1058 친구 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람� www.acmicpc.net 친구, 친구의 친구가 가장 많은 사람의 친구 수를 출력하는 문제이다. 거리가 2 이내인 정점의 개수의 최댓값을 구하면 되므로 각 정점마다 BFS로 체크하다 거리가 2 이상 넘어가면 탈출하도록 코드를 짜고 최댓값을 취합해 출력하면 된다. Code #include #define ll long long using namespace std; ll N, ans=0; string arr[55]; ll BFS(ll st){ ll visit[55], re..

문제 : 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 팰린드롬 만들기