35개의 댓글이 있습니다.

• 
  sven

  "3시간씩 앞으로 움직인다." 의 정의가 약간 모호한데요,
  12->3->6->9 순으로 움직인다는 뜻입니다.
  이걸 반대로 해석해서 한참 해맸네요. (예제 손으로 풀어보고 눈치챔ㅜㅜ) 예제 입력을 넣었을 때 값이 2, 15로 나온다면 위의 의미를 혼동한 것인지 체크해보시길 바랍니다.

  
  11년 전 link

• 
  JongMan

  오.. 그럴수 있군요. 좋은 지적이십니다 :-)

  
  11년 전 link

• 
  imcme

  "불가능할 경우 -1을 출력한다" 이걸 못보고 계속 고민했네요

  
  11년 전 link

• 
  mulpats

  java 로 풀어보려 하는데 계속 오답이 나오네요...
  전부 12실 만들수 있는 스위치 조합이 2개 이상인 예제 하나만 주세요~ ㅡㅡ; 질문이 좀 이상한가요...

  
  11년 전 link

• 
  Being

  전부 12시에서 거꾸로 눌러 보면 금방 만드실 수 있지 않을까요? :)

  
  11년 전 link

• 
  mulpats

  예제를 풀었을때 결과가
  [ 0 0 0 0 0 0 0 0 2 ]
  2
  [ 1 1 0 1 0 2 3 1 ]
  9
  이런 결과가 나옵니다. 괄호안의 값은 스위치가 몇번 눌러졌는지 횟수 입니다. 근데 답안제출하면 오답이 나오네요... ㅡㅡ; 개발10년차 되가는데 너무 어리버리 하네요... ㅠㅠ

  
  11년 전 link

• 
  KOINICHI

  배열 초기화 할 때 콤마 말고 점을 찍어버려 하루 종일 고민했네요 ㅠㅠ

  
  10년 전 link

• 
  Jyui

  스위치와 연결된 시계 입력시 오타 주의하세요 ㅠㅠ 오타 찾으니 정답이네요 ㅎㅎ

  
  10년 전 link

• 
  Being

  아이고 종종 있는 일이지요 :)

  
  10년 전 link

• 
  sypark9

  예제 및 제가 만든 테스트 케이스에서 모두 정답이 나오는데, 정답제출하면 오답뜨네요.
  계속 코드를 보구는 있는데 잘못된 점을 못 찾구 있어요 ㅜ ㅜ

  
  10년 전 link

• 
  sypark9

  시계데이터 배열을 10X16 으로 하지 않고, 10x5로 하고, 하나의 스위치에 5개 미만이 연결된 경우 뒷부분을 -1로 입력했는데, 몇군데서 이 -1을 빼먹어서 오답처리된 경우였습니다.
  며칠동안 엉뚱하게 로직만 주구장창 보다 포기했었는데...흑
  잘못이 예제에서는 정달을 냈고, 실제 검증에서 이 부분이 걸렸던 것도 신기하네요.
  암튼 성공해서 기분좋습니다. ㅎㅎㅎ

  
  10년 전 link

• 
  Jaekwan

  완전 탐색 말고 다른 방법론이 적용 가능한건가요?

  python으로 만드는데 시간 초과가 나오네요..

  
  9년 전 link

• 
  Being

  여러 방법이 있기도 하지만, 제가 보기에는 완전 탐색을 구현한 올바른 파이썬 답안이 충분히 많이 있는 것 같습니다.

  
  9년 전 link

• 
  jurampark

  완전탐색으로 풀 경우에 4^10에 시계를 돌리기위한 For문을 도는것과 모두 12시를 가리키고 있는지 확인하는것을 생각하면 4^10 * 40 * 10 정도의 시간이 걸릴것같은데.. 약 4억정도로 시간이 간당간당하지 않나요?

  
  9년 전 link

• 
  yangjy0113

  C++로 구현했는데 main을 1로 리턴했더니 RTE에러가 나네요.

  
  8년 전 link

• 
  슈크

  불가능한 경우 -1 출력하는걸 깜빡해서 한참을 헤맸네요.......
  저만 이리 바보같은 짓을 하는건가요......허허허허

  
  8년 전 link

• 
  Elevista

  혹 타이핑 하기 귀찮으신 분들을 위해..
  C++11 이상부터
  

  vector<vector<int> > button({
      vector<int>( { 0, 1, 2 }),
      vector<int>( { 3, 7, 9, 11 }),
      vector<int>( { 4, 10, 14, 15 }),
      vector<int>( { 0, 4, 5, 6, 7 }),
      vector<int>( { 6, 7, 8, 10, 12 }),
      vector<int>( { 0, 2, 14, 15 }),
      vector<int>( { 3, 14, 15 }),
      vector<int>( { 4, 5, 7, 14, 15 }),
      vector<int>( { 1, 2, 3, 4, 5 }),
      vector<int>( { 3, 4, 5, 9, 13 })
  });
  

  
  8년 전 link

• 
  yhtgogo

  미지수는 10개
  방정식은 16개
  충분히 풀 수 있는 상황인데요.
  시간을 만족할지는 두고봐야겠군요.

  
  8년 전 link

• 
  yhtgogo

  8번, 12번 시계는 한 세트구요. (4번스위치)
  14번, 15번 시계도 한 세트로 봐도 되겠네요. (2, 5, 6, 7번 스위치)
  이들 세트가 각기 다른 값으로 입력되면 영원히 맞출 수 없다는 것!
  여튼 어렵습니다.

  
  8년 전 link

• 
  wkdqhddnjs12

  그냥 각 스위치마다 0번 1번 2번 3번이렇게 4가지로 해서 하면 대충 4의 10승이 나와서 다른 경우를 고려해도 얼추 10초안에는 되더라고요

  
  8년 전 link

• 
  yongsoo.yoo

  array의 첫번째 address를 length로 가지면 index를 바로 찾아가지요

  const int *CLOCK[10] =
  {
  new int[4]{ 3, 0, 1, 2 },
  new int[5]{ 4, 3, 7, 9, 11 },
  new int[5]{ 4, 4, 10, 14, 15 },
  new int[6]{ 5, 0, 4, 5, 6, 7 },
  new int[6]{ 5, 6, 7, 8, 10, 12 },
  new int[5]{ 4, 0, 2, 14, 15 },
  new int[4]{ 3, 3, 14, 15, },
  new int[6]{ 5, 4, 5, 7, 14, 15, },
  new int[6]{ 5, 1, 2, 3, 4, 5 },
  new int[6]{ 5, 3, 4, 5, 9, 13 },
  };

  void moveClock(int solvClock[], int cNum)
  {
  for (int i = 1; i <= CLOCK[cNum][0]; i++)
  if ((solvClock[CLOCK[cNum][i]] += 3) > 12)
  solvClock[CLOCK[cNum][i]] = 3;
  }

  
  7년 전 link

• 
  wddtev

  휴..예제입력해도 출력이 알맞게 되고 불가능할 경우 -1 출력도 해놨는데 왜 ..왜 제출만 하면 오류가 뜨는지 원..ㅠㅠ

  
  7년 전 link

• 
  cosics

  아.. 같은 스위치가 여러 번 눌려져도 시간만 맞으면 정답인게죠? 그렇다면 멱집합으로 풀면 안되겠군요..

  
  7년 전 link

• 
  cosics

  Repeated Permutation으로 푸는 문제였네요. N=4이고 R=10인데.. N이 4인 이유는 책에서 설명해 놓아서 풀었습니다. 처음에 중복순열을 적용해야 할 것 같았지만 N을 4로 제한하는 것이 이해가 안되었죠. 물론 4 * 3 해보면 제자리로 돌아오긴 했지만.. 여러 스위치를 조합하여 움직일 때 N이 반드시 4 이하 일까?라고 생각했습니다. 사실 이 부분은 좀 더 생각해 봐야 할 것 같구요. 최소한의 횟수이긴 하지만 왠지 N이 4를 넘기는 특이한 경우가 포함된 경우의 수가 더 최소의 횟수가 될지도 모른다는 생각이 드네요. 증명을 시도해봐야 겠습니다.

  
  7년 전 link

• 
  luku756

  이 문제가 노린 것인지 우연인지는 모르겠습니다만, 수학적인(?) 접근으로 상수 시간에 풀수 있습니다. 0ms 나왔네요.

  스위치-시계 로 되어있는 표를 시계-스위치 로 바꿔서 늘어놓아 보면 재미있는 걸 발견하실 수 있습니다.

  
  6년 전 link

• 
  simm4256

  딱히 노린 건 아닌 것 같지만 재미있는 특성이네요.
  문제의 의도가 4^10의 완전탐색이라면 스위치와 시계의 관계를 조금 수정해야 할 필요가 있겠네요.

  
  6년 전 link

• 
  hahanbyul

  
  1차 연립방정식을 풀면 완전 탐색보다 빨리 풀 수 있습니다.
  

  
  6년 전 link

• 
  virtusshin

  파이썬3의 경우 완전 탐색 시간초과가 걸려서 약간의 수정이 필요했습니다.

  
  6년 전 link

• 
  corruptangle

  4^10방법을 썼는데 스위치를 이용해 돌린 후 다시 입력된 Colck으로 변경해 주지 않아 삽질 했네요. 변경하니 잘 됩니다.

  
  6년 전 link

• 
  dnjsdlghdi

  정말 다 맞는데 안되길래
  정답 찾아서 하나씩 고치면서 계속 제출해봤는데
  답뒤에 \n안쓰면 틀렸다고 처리되네요....

  
  6년 전 link

• 
  kimsangseob

  visual studio에서 코딩하다가 도저히 속도가 안나와서
  이게 풀릴까 고민했는데, 릴리즈 모드로 변경하고 컴파일하면 어마무시한 속도로 풀어버리네요. 혹여나 비주얼스튜디오에서 디버깅모드로 컴파일 하셔서 저처럼 좌절하지 마시길

  
  5년 전 link

• 
  KkanTo

  안녕하세요? 혹시 파이썬3의 경우에 시간초과를 어떻게 해결하셨는지 여쭤도 될까요?! 알고리즘은, 알고리즘 문제 해결 전략에 나와있는대로 구현을 하였습니다.

  
  5년 전 link

• 
  g6ling

  파이썬의 경우는 시계랑 스위치랑 1대1 대응이 되는 스위치 들이 있어서 이 부분은 건너띄고 하는 것으로 처리하였습니다.

  # from typing import Dict, List
  from collections import deque, defaultdict, OrderedDict, Counter
  from heapq import heapify, heappush, heappop
  from bisect import bisect_left, bisect_right
  from functools import lru_cache
  from itertools import combinations, permutations
  import re
  import sys
  inf = float('inf')
  sys.setrecursionlimit(10**9)
  MOD = 10**9+7
  
  
  def solve(clocks):
      clocks = [num // 3 % 4 for num in clocks]
      switches = [
          [0, 1, 2],
          [3, 7, 9, 11],
          [4, 10, 14, 15],
          [0, 4, 5, 6, 7],
          [6, 7, 8, 10, 12],
          [0, 2, 14, 15],
          [3, 14, 15],
          [4, 5, 7, 14, 15],
          [1, 2, 3, 4, 5],
          [3, 4, 5, 9, 13]
      ]
  
      def create(idx, arr):
          if idx == len(arr):
              yield arr
              return
          if idx in [1, 4, 9]:
              yield from create(idx+1, arr)
              return
          for i in range(4):
              arr[idx] = i
              yield from create(idx+1, arr)
              arr[idx] = 0
      ans = inf
      base = [0]*len(switches)
      base[9] = (4-clocks[13]) % 4
      base[4] = (4-clocks[12]) % 4
      base[1] = (4-clocks[11]) % 4
      for arr in create(0, base[:]):
          cur = clocks[:]
          for i, a in enumerate(arr):
              for s in switches[i]:
                  cur[s] = (cur[s]+a) % 4
          if all(c == 0 for c in cur):
              ans = min(ans, sum(arr))
      return ans if ans != inf else -1
  
  
  t = int(input())
  for _ in range(t):
      print(solve(list(map(int, input().split()))))
  

  
  3년 전 link

• 
  g6ling

  참고로 꽤나 쉬운 방정식으로 구성 되어 있기 때문에 그냥 스위치랑 시계의 관계의 방정식 손으로 풀어서 넣어도 충분히 파이썬으로 정답 될 있을 것 같습니다.

  
  3년 전 link

• 
  kravi

  -1 없는 테스트 케이스 10개입니다.
  IN :
  10
  3 6 6 12 3 3 9 9 6 6 6 6 6 12 6 6
  12 3 6 12 6 6 6 12 12 12 12 3 12 9 6 6
  3 12 12 12 3 3 6 9 9 9 9 12 9 9 12 12
  9 3 3 9 6 12 3 6 3 3 9 6 3 9 3 3
  12 9 6 6 12 6 6 6 6 12 12 6 6 6 9 9
  12 9 3 3 6 9 3 6 3 9 12 3 3 6 6 6
  3 12 6 12 6 12 12 6 3 9 9 6 3 3 3 3
  12 12 12 9 6 12 12 3 9 3 3 12 9 3 12 12
  6 12 12 12 6 9 3 3 12 3 9 9 12 6 12 12
  3 12 12 9 9 6 6 12 6 9 9 9 6 12 3 3

  OUT:
  0 2 0 3 2 0 0 2 2 0 ; 11
  3 3 0 2 0 3 0 3 0 1 ; 15
  2 0 0 1 1 0 1 3 2 1 ; 11
  1 2 2 0 3 0 0 1 2 1 ; 12
  3 2 2 0 2 1 0 2 2 2 ; 16
  2 3 1 0 3 2 3 0 3 2 ; 19
  0 2 2 1 3 2 3 0 0 3 ; 16
  1 0 2 3 1 0 3 3 3 3 ; 19
  3 1 1 3 0 0 0 3 1 2 ; 14
  3 1 3 0 2 0 3 1 1 0 ; 14

  
  3년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.