방구석프로의 이야기

https://www.acmicpc.net/problem/20055

문제 해결을 위한 과정

이 문제의 경우 구현 문제로 문제에서 요구하는 바를 그대로 코드로 작성하면 해결할 수 있는 문제였습니다. 

과정은 다음과 같습니다.

1. 로봇과 벨트를 함께 이동

2. 먼저 올린 순서대로 로봇 이동(먼저 올린 순서는 n-1번째부터 0번째까지 역순으로 이동하면 쉽게 해결 가능)

3. 로봇을 0번째에 올리기

4. 내구도가 0인 벨트의 수가 K 이상인지 확인하기.

단, 이때 2번, 3번 과정은 해당하는 벨트의 내구도가 1 감소한다는 것 그리고 1번, 2번 과정은 n-1번째에서 로봇이 내린다는 것을 적용하면 해결할 수 있습니다.

소스코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
robotInfo = []

ans = 0
for i in range(len(arr)):
  robotInfo.append((arr[i], ''))
  
while True:
  ans += 1
  # 1단계
  temp, robot = robotInfo[2*n-1]
  for i in range(2*n-1, 0, -1):
    robotInfo[i] = robotInfo[i-1]
  robotInfo[0] = (temp, robot)
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")

  # 2단계
  for i in range(n-1, -1, -1):
    temp, robot = robotInfo[i]
    if robot != "":
      nextTemp, nextRobot = robotInfo[i + 1]
      if nextTemp >= 1 and nextRobot == "":
        robotInfo[i] = (temp, "")
        robotInfo[i + 1] = (nextTemp-1, "exist")
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")
  
  # 3단계
  temp, robot = robotInfo[0]
  if temp >= 1:
    robotInfo[0] = (temp-1, "exist")

  # 4단계
  cnt = 0
  for i in range(0, 2*n):
    temp, robot = robotInfo[i]
    if temp == 0:
      cnt += 1
  if cnt >= k:
    break
print(ans)

https://www.acmicpc.net/problem/11723

문제 해결을 위한 과정

이 문제의 경우 알고리즘의 분류상 구현 문제로 문제에서 주어진 대로만 차분하게 구현하면 쉽게 해결할 수 있는 문제였습니다. 다만 실버 5 티어라는 난이도에 비해 정답률이 29%로 낮은 편인데 그 이유는 메모리 제한 때문이라 생각됩니다. 저 역시 pypy3로 풀었을 때 메모리 초과 판정을 받았고 pypy는 시간 복잡도가 좋은 대신 공간 복잡도 측면에서 불리하다는 사실을 알게 되어 python3으로 해결한 결과 정답 판정을 받을 수 있었습니다. 문제의 조건을 그대로 구현하면 되는 문제이기 때문에 해결방안은 따로 제시하지 않습니다.

소스코드

https://www.acmicpc.net/problem/14499

문제 해결을 위한  과정

이 문제의 경우 골드 4 티어로 비교적 높은 난이도를 가지고 있지만 사실 구현으로 분류되는 문제의 특성상 차분하게 문제에서 제시한 조건을 따라가면 쉽게 해결할 수 있는 문제였습니다. 다만 주사위라는 공간지각 능력이 필요한 문제라서 조금 생각을 해야 합니다. 이 문제를 푸는 데 있어서 가장 중요한 것은 전개도입니다. 전개도 대로 주사위를 만들면 아래의 그림과 같습니다. 

이를 동쪽, 서쪽, 남쪽, 북쪽으로 돌리더라도 주사위의 특성상 마주보는 면의 합은 7입니다. 위 주사위 그림의 면에 배정된 숫자는 문제에서 주어진 조건 "주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여 있는 곳의 좌표는 (x, y)이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다." 를 반영한 것입니다. 즉 위치를 저렇게 잡은 후 모든 주사위의 면을 0으로 초기화합니다. 그 후 문제에서 테스트 케이스로 주어진 지도에 0행 0열에 주사위를 배치합니다. 첫 번째 예시에서 맵은 다음과 같습니다.

과정 및 주사위 그림은 다음과 같습니다.

1. 시작지점에 위치(0행 0열)

2. 명령이 4 이므로 남쪽으로 회전 1행 0열이 3 이므로 주사위의 밑면은 3, 윗면은 0이 됨 따라서 0 출력

3. 명령이 4 이므로 남쪽으로 회전 2행 0열이 5 이므로 주사위의 밑면은 5, 뒷면은 3, 윗면은 0이 됨 따라서 0 출력

4. 명령이 4 이므로 남쪽으로 회전 3행 0열이 7 이므로 주사위의 밑면은 7 뒷면은 5 윗면은 3이 됨 따라서 3 출력

5. 명령이 1 이므로 동쪽으로 회전 3행 1열이 8 이므로 주사위의 밑면은 8 왼쪽면은 7 오른쪽면은 3 뒷면은 5 윗면은 0 따라서 0 출력

이러한 과정을 반복한다.

문제 해결을 위한 팁

처음의 주사위의 전개도를 2차원 리스트의 형태로 구현한 후 문제를 해결하려 하였으나 예상보다 복잡해지는 바람에 다른 방법을 찾던 중 단순하게 일차원 리스트로 해결할 수 있음을 알게 되었고 해결방법은 다음과 같다. 먼저 리스트를 다음과 같이 설정한다.

dice = [0, 0, 0, 0, 0, 0]

그 후 이 그림을 보면서 항상 리스트의 0번째가 윗면, 1번째가 앞면, 2번째가 오른쪽면 이런 식으로 5번째가 아래쪽면이라는 것을 고정한 뒤 swap을 해준다. 즉 남쪽으로 한번 회전을 해주면 위의 그림에서 왼쪽 오른쪽면은 그대로 있고 나머지 4면이 회전을 하는 형태이다. 따라서 이를 이렇게 표현할 수 있다.

if 남쪽으로 회전할 시:

    dice[5], dice[1], dice[0], dice[4] = dice[1], dice[0], dice[4], dice[5] 

이를 전체의 경우에 적용하면 쉽게 해결할 수 있다. 소스코드는 아래와 같다.

소스코드

https://www.acmicpc.net/problem/2941

문제 해결을 위한 과정

처음에 이 문제를 해결할 때 해당하는 모든 경우의 수를 처리하여 해결하였습니다. 그러나 조금 더 쉽게 해결할 수 있는 방법이 없을까 고민하다 구글링을 통해 새로운 풀이를 알게 되었습니다. 

즉 크로아티아 문제에 해당하는 문자들을 리스트로 구성한 후 해당하는 원소들이 입력받은 문자열에 존재하면 다른 문자로 변경한 후 변경된 문자열의 길이를 세면 됩니다. 소스코드는 다음과 같습니다.

소스코드

https://www.acmicpc.net/problem/11866

문제 해결을 위한 과정

이 문제는 구현 유형의 문제로서 어려운 문제는 아니었지만 문제를 해결하는 데 있어서 생각하는 방식이 중요한 문제였습니다. 문제에서 주어진 예시를 해결해보겠습니다.

다음의 그림은 예시를 푸는 과정입니다. 이 예시에는 N은 7, K는 3입니다.

문제 해결을 위한 팁

이 문제는 위의 그림을 자세히 살펴보면 알 수 있듯이 k번째 원소가 아닌 것들은 다시 뒤에 붙여서 해결한다는 점입니다. 따라서 관찰을 통해 큐를 구현하면 해결할 수 있음을 알 수 있습니다. 파이썬에서 큐 보다 효율적인 deque를 이용해 popleft(), append()를 이용해 해결할 수 있습니다.

소스코드