본문 바로가기

알고리즘/백준42

[백준] 1780 종이의 개수 예전에 풀어봤던 문제인데 해맸다. 0,1,-1의 개수를 세어 주고 n*n개 인지 비교하고 아니면 분할하는 방식으로 했는데 왜인지 계속 정답이 안나왔다. 재귀가 잘못된건지 뭐가 잘못된건지 못찾아서 다른 방식으로 했다. 하나라도 다른 것이 있으면 분할하고 아니면 카운트 해주었다. #include #include using namespace std; int nn,temp; int num[2200][2200]; int ans[3]; int check; void division(int x, int y, int n) { check = num[x][y]; for (int i = x; i < x + n; i++) for (int j = y; j < y + n; j++) { if (num[i][j] != num[x][y.. 2022. 6. 4.
[백준] 2839설탕배달 c++ dp문제이다. 2중 for문을 통해서 풀어줬다. 3키로 봉지와 5키로 봉지와 조합을 해서 만들 수 있는 무게여야하고 최소의 개수의 봉지를 사용해야한다. sugar[3]과 sugar[5]를 1로 초기화 해줬다. 해당 무게를 만들 수 있는 조합을 안에 있는 for문으로 다 검사해주어서 최소의 개수를 sugar[i]에 넣어주었다. #include #include using namespace std; int sugar[5001]; int main() { int n; cin >> n; for (int i = 0; i < 5001; i++) sugar[i] = 5000; sugar[3] = 1; sugar[5] = 1; for (int i = 3; i 2022. 5. 28.
[백준 ] 2042 구간합 구하기 C++ 두번째 풀었던 것임에도 놓쳤던 부분 1.배열 크기를 int 로 했다.-> long long으로 해야한다. 2. 세그먼트 트리 크기를 num 배열이랑 똑같이 해줬다. -> 4배 해야한다. 3.(start+end)/2 로 해야하는데 start+end/2로 했다. ->코드 꼼꼼히 작성하기 4. 함수를 호출할때 num배열은 0에서 N-1까지이기 때문에 start=0,end=N-1로 해줘야하는데 1과 N으로 했다. 다음에는 num배열을 1부터 입력을 받아야겠다. +(b인덱스의 값을 c로 바꾸는 부분도 틀렸다.) 5. 배열의 값을 갱신 시켜줄때 원래 값과 차이를 이용하면 되는데 까먹었다. 다시 한번 풀어봐야겠다. #include #define MAX_TREE (1 right || end < left) return .. 2022. 5. 22.
[백준] 1992 쿼드트리 c++ https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 예전에 풀어봤던 분할 문제하고 비슷해서 금방 풀었다. 1.n*n 크기의 사각형을 검사한다. 2.전부 0이거나 1이면 문자열에 0이나 1을 추가해준다. 3. 아니면 문자열에 (을 추가하고 n/2*n/2 크기의 사각형 4개로 분할해서 사각형을 검사한다. 4. 분할한 사각형을 다 검사하면 )을 문자열에 추가한다. *입력이 문자열로 들어오기 때문에 잘라서 int로 바꿔서 배열에 넣어줘야한다... 2022. 5. 14.

티스토리툴바