본문 바로가기

Problem

[C/C++] BOJ 1932 :: 정수 삼각형 BOJ 1932 :: 정수 삼각형 문제 링크 : https://www.acmicpc.net/problem/1932 나의 풀이 1. 정수삼각형의 값을 2차원 배열에 저장한다. 2. 각 층마다 최댓값을 저장한다.삼각형의 가장 왼쪽 값은 바로 윗층의 같은 열의 값 + 현재 값을 저장한다.삼각형의 가장 오른쪽 값은 바로 윗층의 현재 열 - 1 의 값 + 현재 값을 저장한다.나머지 값은 그 둘 중 최댓값 + 현재 값을 저장한다. if (j == 0) arr[i][j] += arr[i-1][j]; else if (j == i) arr[i][j] += arr[i - 1][j - 1]; else arr[i][j] += max(arr[i - 1][j], arr[i - 1][j - 1]); 3. 마지막 층 중에서 최댓값을..
[C/C++] BOJ 2163 :: 초콜릿 자르기 BOJ 2163 :: 초콜릿 자르기 문제 링크 : https://www.acmicpc.net/problem/2163 규칙이 매우 간단하여 O(N)이 아닌 O(1)로 풀 수 있는 문제! 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_2163/BOJ_2163.cpp 12345678910111213// 백준알고리즘 2163번 :: 초콜릿 자르기 #includeusing namespace std; int N, M, ans;int main(void){ cin >> N >> M; ans = N*M - 1; cout
[C/C++] BOJ 11052 :: 카드 구매하기 BOJ 11052 :: 카드 구매하기 문제 링크 : https://www.acmicpc.net/problem/11052 나의 풀이 학부 고급알고리즘 시간 때 배운 Knapsack 알고리즘을 생각하며 풀었다! 1. 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값은 카드 1개가 포함된 카드팩의 가격이므로 그 값을 그대로 저장한다. 2. 카드 2개부터는 지금까지 저장한 카드를 갖기위해 지불해야 하는 금액의 최댓값과 카드팩의 가격을 이용하여 비교한 후 갱신한다. Ex) 카드 2개를 갖기 위해 지불해야 하는 금액의 최댓값은 1) 카드 0개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카드 2개가 포함된 카드팩의 가격 = 5현재 저장되는 최댓값은 52) 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카..
[C/C++] BOJ 2306 :: 유전자 BOJ 2306 :: 유전자 문제 링크 : https://www.acmicpc.net/problem/2306 처음에는 다이나믹 프로그래밍이니까 무조건 하나의 반복문 루프 안에서 끝내야 한다는 생각에 사로잡혀 한 번의 루프로 끝낼 수 있는 규칙을 찾지 못해 난관에 빠졌었다, 생각을 바로잡고 문제에 나와있는 규칙을 적용하여 재시도한 결과, 얼추 규칙에 맞는 프로그래밍을 할 수 있었다. 그러나 계속 틀렸습니다. 가 떠서 백준 슬랙을 통해 문의한 결과 ㅠㅠ 간과한 점을 알 수 있었다. 나는 2번 조건과 3번 조건을 각각의 반복문으로 진행시켜 주었는데 그러면 atat와 같은 KOI 유전자의 길이를 제대로 도출해낼 수 없었다. 따라서 같은 루프 안에서 2번 조건과 3번 조건을 함께 판단하는 것으로 코드를 변경함으로..
[C/C++] BOJ 2234 :: 성곽 BOJ 2234 :: 성곽 문제 링크 : https://www.acmicpc.net/problem/2234 나의 풀이 - 비트연산으로 이웃한 칸에 갈 수 있는지 확인하면서 그룹을 짓는다. if (castle[x][y] & (1
[C/C++] BOJ 1938 :: 통나무 옮기기 BOJ 1938 :: 통나무 옮기기 문제 링크 : https://www.acmicpc.net/problem/1938 나의 풀이 - 통나무 중간 부분 좌표와 방향이 있으면 통나무의 모양을 알 수 있다. => 통나무의 중간 부분과 방향으로 탐색을 진행한다. 1. 상하좌우 방향에 따라 상하좌우로 움직였을 때, 지도를 벗어나면 continue2. 움직일 수 없는 공간이면 continue3. 이미 방문한 지점이면 continue그 외에는 queue에 넣는다. 1. 상하좌우에 대각선을 포함하여 8방향이 지도를 벗어나면 break2. 움직일 수 없는 공간이면 break3. 방문하지 않은 지점이면 queue에 넣는다. 처음 코드를 제출했을 때 실수를 했는데 회전 탐색시 방문 여부를 판단할 때이다. 조건문 안에서 조건문..
[C/C++] BOJ 1890 :: 점프 BOJ 1890 :: 점프 문제 링크 : https://www.acmicpc.net/problem/1890 자료형의 출력범위를 혼동해서.. unsigned int 로 했다가 틀렸다 ㅠㅠ 한 번에 맞출 수 있었는데... 그래도 문제를 보고 접근방식이 바로 생각났고 생각대로 코딩하여 답을 맞출 수 있어서 매우 뿌듯했다! 나의 풀이 DFS + DP 방식으로 문제 풀기 반환 조건1. 종착역에 도착하면 1 반환2. 이미 dp 배열에 값이 있으면 그 값 반환3. 현재 board의 값이 0 이면 0 반환 반환된 값을 더하여 dp 배열 갱신 ============================================================== 나의 풀이 방법말고 처음부터 끝까지 순차적으로 dp 배열을 채워나가..
[C/C++] BOJ 1600 :: 말이 되고픈 원숭이 BOJ 1600 :: 말이 되고픈 원숭이 문제 링크 : https://www.acmicpc.net/problem/1600 나의 풀이 >> 방문 여부를 확인하는 배열을 3차원으로 만든다. // 방문 여부 [x좌표][y좌표][말같이 움직인 횟수]int visited[201][201][31]; - K만큼 말같이 이동하지 않았으면, 말같이 이동하는 경우를 queue에 갱신시킨다.- 원숭이가 이동하는 경우를 queue에 갱신시킨다.- 도착지점에 도달하면 return 한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1600/BOJ_1600.cpp 1234567891011121314151617..

티스토리툴바