그릇 모으기 문제 n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다. 문제 풀이 문제를 좀 더 단순화하여 약한 조건으로 생각해보자.0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는..
삼성 소프트웨어 역량테스트 대비 문제 추천 14499 주사위 굴리기12100 2048(Easy)13460 째로탈출 213458 시험 감독10875 뱀2468 안전 영역1938 통나무 옮기기1600 말이 되고픈 원숭이2931 가스관1937 욕심쟁이 판다2638 치즈9376 탈옥5427 불3055 탈출1726 로봇2169 로봇 조종하기1194 달이 차오른다, 가자.2156 포도주 시식11727 2xn 타일링 211055 가장 큰 증가 부분 수열11066 파일 합치기2602 돌다리 건너기1022 소용돌이 예쁘게 출력하기3020 개똥벌레1939 중량제한3079 입국심사
주사위 굴리기 문제 지도 위에서 주어진 명령에 따라 주사위를 굴린다. 각 명령에 대해서 주사위 맨 윗면의 값을 출력하는 문제이다. 문제 풀이 시뮬레이션 문제이다. 명령이 K번 존재하므로 \(O(K)\)로 해결가능하다. 주어진 그림과 같이 항상 맨 윗면이 1 바닥과 닿아 있는 면을 6으로 생각하고 구현해보자. 오른쪽으로 구르는 경우를 예시로 들면 1. 먼저 구를수 있는지 판단(다음 좌표가 지도 내부인지) 2. 다음 주사위 상태에서 2번과 5번 면은 변하지 않는다. 오른쪽이므로, 현재 1번 면이 다음 3번 면으로 현재 4번 면이 다음 1번 면으로 현재 6번 면이 다음 4번 면으로 현재 3번 면이 다음 6번 면으로 바뀌게 된다. 3. 다음 상태공간을 만들었다면 6번 면과 지도 값을 비교하여 문제에 주어진 조건..