백준 문제풀이

1813번: 논리학 교수 (acmicpc.net)  상당히 쉬운 실버5 문제이다. 문제가 겉보기 난이도가 좀 있는데, 묻고자 하는 바를 똑바로 살펴보면 금방 풀 수 있는 문제이다.  우선 n개의 말이 참이다 라는 문장이 n개가 등장했다면 그것이 답이 될 것이다.  그렇다면 배열에 인덱스에 값들을 넣어놨다가, 일일이 확인해보면서 내려가면 답을 찾을 수 있지 않을까? 라는게 나의 생각이었고, 단박에 통과했다. 아래는 C++로 작성한 코드이다.#include #include using namespace std;int num, what;int cham[51] = {0,};int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin ..

12865번: 평범한 배낭 (acmicpc.net)  분명 알고 있는 알고리즘이고 금방 구현할 것이라고 생각했는데,, 최근에 일차원 DP 배열 문제들만 풀다 보니 DP 2차원 배열을 생각하지 못한 것이 패착이었다. 결국 시간을 질질 끌고 풀었다..  2차원 배열에 각각 행과 열을, 가방에 담을 수 있는 최대 무게와 1~i 번째 물건까지 고려한 경우를 나타내게 설정한다.  생각해보면 다음의 알고리즘이 성립한다. i번째 물건의 무게가 현재의 리미트 무게보다 큰 경우당연히 담을 수 없으니 패스한다.작은 경우그 물건을 넣는 경우현재 가방의 최대 무게가 limit라면, limit-그물건의무게 에서의 값 + 그 물건의 Value 값이 배열의 값이 될 것이다.그 물건을 넣지 않는 경우현재 가방의 최대 무게가 limi..

13549번: 숨바꼭질 3 (acmicpc.net)  골드 문제 중에서는 쉽게 접근하고 쉽게 코드 구현이 가능한 문제 중 하나라고 생각한다.  Dynamic Programming 기법을 사용하면 쉽게 구현할 수 있을 것이라고 생각했고, visited 배열의 방문 확인을 통해 최단 거리에 이미 도달한 적이 있었던 숫자의 방문을 막는다.  BFS 기법을 사용하여 Queue에다가 넣고 빼면서 확인하는데, 하나 고려해야 하는 점은 최단 거리이기 때문에, 문제에서 제시하는 조건을 잘 읽어봐야 한다.  곱하기 2를 하는 행동은 0초지만, 하나를 더하거나 빼는 행위는 1초가 걸리기 때문에, 최단 거리를 계산할 때는 반드시 곱하기 2를 먼저 하는 경우의 수를 생각해야 한다.  이 고려사항을 큐에 먼저 넣어준다 라는 개..

2096번: 내려가기 (acmicpc.net) 개인적으로 문제 해결은 쉬웠지만, 메모리 제한을 해결하기 위한 메모리 상식을 다시 공부할 수 있어서 좋았던 문제였다.글 읽기 - 정답이지만 메모리초과 질문 있습니다! (acmicpc.net)백준 질문 게시판을 돌아다니다 발견한 메모리 관련 좋은 글로, 위 글에는 다음과 같은 설명이 적혀있다. 채점 결과의 메모리 사용량에 잡히는 것은 배열이 전부가 아닙니다. 1000번 A+B 문제처럼 변수 2개가 고작인 코드도 결과를 보면 아마 2020KB라는 사용량이 찍힐 것입니다. cin, cout을 사용하는 것만으로 기반 클래스 객체 생성 & 버퍼 용량 확보가 진행되기 때문입니다. scanf/printf로 바꿔도 1112KB나 1116KB 같은 값을 보게 될 것입니다. ..