개발하는 kim-hasa

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 맨 위에서부터 내려왔을 때 , 가장 큰 점수를 획득하는 경우를 구하는 문제입니다. 반대로 생각하면 , 아래에서 맨 위로 올라갔을 때 가장 큰 점수를 구하면 됩니다. 특정 점 [ i , j ] 의 최대값은 [ i + 1][ j ] , [ i + 1 ][ j + 1 ] 중에 큰 수를 구해서 정하고, [ i , j ] 가 [ 1 , 1 ]이 될 때까지 올리면 됩니다. #include using namespace std; int arr[501][501] = {0}; int m..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 힙의 마지막 문제 절대값 힙 문제입니다. 이전 두 힙과는 다르게 , 절대값으로 비교해야 합니다. 우선순위 큐에 pair 함수를 써서 , 절대값으로 정렬 된 후 2번째 인자로 음수인지 양수인지를 넣어서 정렬합니다. 그 이후 절대값으로 비교하고 작은 수(음수) 부터 출력합니다. #include #include #include using namespace std; int main(..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 배열에서 최대의 값을 출력하는 문제입니다. 우선순위 큐를 사용했습니다. 0이 들어오면 큐에서 가장 맨 앞 숫자를 출력하면 됩니다. #include #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; prio..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 숫자를 입력받아서 , 0이 입력되는 경우 배열에서 가장 작은 값을 리턴하는 문제입니다. 우선순위 queue를 적용했고 , 오름차순으로 정렬했습니다. 다만 개수가 많아서 시간초과 이슈가 있어서 , 입출력 속도를 빠르게 하는 코드가 필요합니다. #include #include using namespace std; int main(){ ios_base :: sync_with_stdi..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 이전에 풀었던 색종이 문제들이랑 비슷한 문제입니다. 다만 순서에 조금 신경써야 한다는 점 ?? 똑같이 같으면 문자열에 추가하고 , 아니면 나눕니다. 나눌 때 , 괄호가 들어가므로 앞뒤에 괄호만 삽입해주면 됩니다. #include #include using namespace std; int arr[64][64] = {0}; string ans = ""; void find(int x, i..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 색종이와 비슷한 문제입니다. 역시 같은 것만 있는지 체크하고 , 다른게 있다면 나눕니다. 3등분으로 나누는데 조금 애를 먹긴 했습니다. 가운데 index가 헷갈려서 .. 그러다 반복문으로 돌리는 방법으로 바꾸어서 해결했습니다. #include using namespace std; int arr[2200][2200] = {0}; int ans[3] = {0}; void find(int x..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 색종이에 같은 숫자가 있는 사각형끼리 모아서 잘라내는 문제입니다. 가장 먼저 , 색종이가 1로만 이루어져 있는지 0으로만 이루어져 있는지 체크합니다. 섞여있다면 , 4등분 하고 다시 1과 0으로만 이루어져 있는지 체크합니다. 섞이지 않았다면 , 1 또는 0으로만 이루어져 있으므로 count를 체크합니다. 마지막에 1칸짜리만 남았다면 , 그 칸이 1인지 0인지 확인해서 카..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제가 재미있었다. 근데 너무 길어서 이해하기는 좀 힘듬 ... 포켓몬을 도감에 입력하고 출력하는 문제였다. 처음엔 그냥 벡터를 사용했는데 , 시간 초과가 나서 map을 사용했다. string 배열과 map에 데이터를 입력해놓고 , 찾아서 출력하면 완성이다. 다만 , 입력이 워낙 많기 때문에 벡터보다는 map을 사용해야 한다. #include #include #incl..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 특정 문자열을 입력받고 , 문자열 안에 특정 IOI...OI가 몇개 있는지 구하는 문제입니다. 기본 아이디어는 k길이의 IOI문자열 안에 n 길이의 IOI 문자열의 개수는 (단 , k >= n ) 1 + (k - n)/2 개 들어갈 수 있습니다. 문자열을 입력받고 , IOI 문자열의 길이를 구합니다. 문자열의 길이가 기본 문자열의..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호가 없는 수식에 괄호를 씌워서 최대한 작은 숫자를 만드는 문제입니다. +인 경우 그냥 더하다가 , -가 나오는 순간 괄호를 씌웁니다. 그 이후 , 덧셈은 계속 minusSum에 더해줍니다. 그러다 -가 나오는 순간 , 괄호를 앞에 씌워서 지금까지 더한 minusSum을 sum에서 빼줍니다. 또한 마찬가지로 minusSum을 0으로 만들고 다시 더합니다. 마지막에 숫자가 하나 남는데 , -..