본문 바로가기

백준 문제 풀이

 (152)
백준 1932 정수 삼각형(C++) DP의 기본적인 문제. 프로그래머스에서는 같은 문제가 레벨3로 어려운 문제에 속했는데 백준에선 실버 판정을 받았다. 하삼각행렬로 삼각형을 저장하고 각 행렬의 숫자를 적절하게 갱신해주면 되는 문제다. #include #include using namespace std; int DP[501][501]; int main() { int n; cin >> n; for (int i = 0; i > DP[i][j]; } } for (int i = n - 2; i > -1; i--) { for (int j = n - 2; j > -1; j--) { if (i < j) continue; DP[i][j..
백준 11053 가장 긴 증가하는 수열(C++) 처음 봤을 땐 "엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다. 그런데 정답률이 낮아서 의아했다. 그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중요한 건 문제 해석을 완벽히 해야한다.. 이 문제의 이름을 잘 보자 " 가장 긴 -증가하는- 수열 " 그러니까 예를들어 5 4 3 2 1 이라는 순서로 들어왔을 때 그냥 1 2 3 4 5라고 생각할 수 있지만 이 문제는 "수열" 이다. 순서를 절대 바꾸면 안된다. 그러므로 증가하는 부분 수열의 길이는 1이다. 이 문제는 들어오는 숫자가 과연 증가하는 수열을 만들수 있는가? 물어보는 문제이다. 예를 들어보자! 5 2 4 3 2 순으로 들어왔다고 가정하자. 1) 5가 들어왔을 때 -> 아무것도 없고 처음이므로 증가 하는..
백준 1076 저항(C++) 뭔가 PS하나는 풀고싶은데 머리는 쓰기싫어서 브론즈 문제 하나 풀어봤다! 그냥 열심히 매핑하고 값이 매우 크니까 long long 자료형을 쓰고 쓸대없지만 왜인지 처음에 문자열로 더할 값을 받아서 문자를 정수로 바꿔줬다. #include #include #include using namespace std; map reg; map regi; int main() { reg.insert(make_pair("black", 1)); reg.insert(make_pair("brown", 10)); reg.insert(make_pair("red", 100)); reg.insert(make_pair("orange", 1000)); reg.insert(make_pair("yellow", 10000)); reg.inser..
백준 13913번 숨바꼭질 4 (C++) 시험기간엔 PS가 재밌어진다 ㅎ 숨바꼭질 1,2,3에 이은 4번째이다. bfs라는 풀이법은 변하지 않았지만 조금 씩 세부적인 사항을 요구한다. 이번에는 지나온 경로에 관해 출력해야한다. 지나온 경로를 출력하는 것에 가장 좋은 방법은 dfs이지만 이 문제에는 "최단거리" 이기 때문에 dfs를 선택하면 무조건 시간초과가 뜬다. 때문에 bfs에서 함수를 더해 경로를 저장해야한다. 그 방법은 배열을 만들고 그 배열에 이전 정보를 저장해놓는 것이다. DP와 비슷하다고 보면 된다. #include #include #include #include using namespace std; queue Q; int currentnumber[100001] = {0,}; int n, m; bool visited[100001] =..
백준 17070번 파이프 옮기기 1(C++) 가장 먼저 생각할 수 있는 방법은 DFS였다. 최소로 이동하는 것도 아니고 각 지점마다 움직일 수 있는 방법이 한정되어있다. 각 노드에서 따질 것이 많다면 DFS가 유리하다. 각 지점마다 방향의 상태를 지정해줘야하기 때문이다. 그런데 이 문제를 보면 시간제한이 1초로 빡세지만 집의 크기가 무려 3~16으로 매우 편하게 주었다. N이 조금만 커져도 이 문제는 dfs bfs로 풀 수 없다. 나름 잘 풀었다고 생각했는데도 시간은 104ms로 오래걸렸다. 이 문제의 의도는 다이나믹 프로그래밍이다. dfs로 최적화하는법도 있겠지만 이문제는 온리 DP로만 풀이가 가능한 것 같다. 채점 현황을 보니 골드 하위정도 티어들은 모두 그래프로 풀고 골드 상위부턴 DP로 풀이했다. 다음에 DP로 다시 풀어봐야겠다. 1. 맨 ..
백준 14503번 로봇 청소기 (C++) 골드 4정돈 되야할 것 같은데 골드5이다. 이 문제는 각 위치에서 따져야 할 것이 많다. 일단 4방향을 봐야하는데 순서가 정해져있고, 바라보는 방향까지 고려해야한다. 게다가 후진까지 한다; (가지가지한다) 그래서 각 위치에서 따져줄 수 있는 DFS 가 맞는 풀이법이다. 시간을 고려해서 문제에서 사이즈도 50까지 크지 않게 주었다. dfs에는 위치정보, 방향정보, 그리고 뒤로 돌아올때는 청소로 치지 않으니 돌아왔는지를 체크한다. dfs를 공부한다면 풀어보면 좋을 것 같은 문제이다. 백준에서는 개인적으로 100줄을 넘어가는 걸 안좋아하는데 방향을 따지고 방향에 따라 순서가 또 달라지니 코드가 길어졌다. 다른 사람들은 나머지연산으로 멋있게 풀었던데 난 그 생각은 나지 않아서 노가다로 모두 적어주었다. #inc..
백준 11866번 요세푸스 문제 0 (C++) 처음 봤을 땐 벡터를 사용할까 생각했다. 그러나 분류를 보니 큐가 있었다. 정말 이걸 왜 생각 못했을까, 이걸 코테에서 만났다면 멍청하게 삽질하다가 시간버렸을 것 같다. 아이디어는 간단하다. 1. 큐에서 front 부터 꺼내면서 K번째가 아니면 다시 큐에 쌓는다. 2. K번째이면 큐에 쌓지 않는다. 3. 큐가 빌 때 까지 반복한다. #include #include using namespace std; int main() { queue Q; int N, K; cin >> N >> K; for (int i = 1; i
백준 1475번 방 번호 (C++) 빡구현 문제다. 예외처리를 해주고 너무 쉽게 생각한 것이 문제였다. 처음엔 112233 이런식으로 들어오면 중복할때마다 카운트 1을 쳤다. 그러나 한 "세트" 가 들어오는데 계속 추가하면 비효율적으로 짜게되는 것을 생각해야한다. 그래서 배열을 만들어 각각 숫자가 몇개 들어오는지 파악하고 가장 큰 수의 세트를 현재 필요 세트라고 생각했다. 그리고 6,9는 함께 사용가능한 것도 생각해야한다. 처음에는 일일히 예외처리를 해주려 했다가 피를 봤다. 잘 생각해보면 6,9를 적절하게 분배하면 되는 거다. 왜냐면 6,9가 일단 0이 아니라면 세트가 존재한다는 것이기 때문이다. 세트가 존재하지 않으면 추가를 해준다. 틀린코드 : #include #include #include #include using namespac..

티스토리툴바