코딩스토리

백준 1043번 - 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 골드 4 치고는 문제가 짧아 보여서 풀었다. 먼저 문제를 이해해보자. 아래는 내가 분석한 문제이다. 1. 진실을 아는 사람이 있는 Party에서는 무조건 거짓말 불가! 2. Party는 (진실을 말함, 거짓을 말함) 두 가지로 나뉜다. 이때 두 가지를 동시에 겪은 사람은 없어야 된다 -> 즉, 어떤 사람이 진실을 들었다면 그 사람이 간 모든 파티에서 진실을 들어야 한다. 3. 만약 진실을 아..

백준 14266번 - 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제는 BFS문제(다이나믹 프로그래밍을 사용한)이다. 최근 풀었던 BFS문제중에 가장 어려웠다. 처음에는 가볍게 queue에 pair로 현재 이모티콘 숫자와 클립보드의 개수를 받아서 풀어보려 했는데 문제의 조건 중 '클립 보드에 복사'라는 조건이 자꾸 걸렸다. 생각해보다가 2차원 배열을 사용하면 될 것 같아서 써봤는데 바로 틀렸습니다.. 디버깅해보니 너무 많은 ..

백준 12852번 - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 BFS, 다이나믹 프로그래밍 문제이다. 처음에는 top-down 방식으로 문제를 해결하려 했다. 문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다. 출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면 dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다. 코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botto..

백준 2206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제는 BFS(너비 우선 탐색) 문제이다. 해결 방법은 3차원 배열을 사용하는 것이다. 보통의 쉬운 수준의 BFS 문제들과 달리 '벽'이라는 장애물이 존재한다. 즉 벽을 부순 횟수를 기억해야 하는데 모든 위치에서 기억해야 하므로 3차원 배열을 사용해야 한다. 다행이 벽을 부술 수 있는 횟수가 1번 이므로 3차원 배열의 크기는 ..