글 읽기 - 반례 요청합니다.

(追記) (追記ここまで)

반례 요청합니다.

1034번 - 램프

lll_lll 1년 전 0

- 문제 풀이 논리

1. 한 행을 String으로 보고, Map<String, Integer> map에 동일한 행의 개수 담기

2. value 기준 정렬한 List<String>으로 탐색 시작

생각한 논리

String에 대해서, 0이 등장할 때마다 zeroCount++

여기서 두 가지 경우의 수를 산정했습니다.

1. zeroCount가 0인 경우 -> K가 짝수라면 원상복귀 가능하기 때문에 그대로 map.get(s)해서 return

2. zeroCount가 0이 아닌 경우

- 1. zeroCount * 홀수 = K여야 함.

- 예를 들어 zeroCount가 2이고, K가 4라면 킨 것을 다시 끄는 경우이므로 x, K는 2, 6, 10, 14 .... 경우만 가능

- 이 논리를 적용하여 K를 zeroCount로 나눈 것이 홀수여야 한다는 식 도출

- 2. K % zeroCount == 0이어야 함. 숫자가 맞지 않다면 일부만 키고 일부는 끄는 현상 발생

테케는 다 맞고 답은 틀리는데, 논리 오류를 모르겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 Map<String, Integer> map = new HashMap<>();
 String[] input = br.readLine().split(" ");
 int N = Integer.parseInt(input[0]);
 int M = Integer.parseInt(input[1]);
 for (int i = 0; i < N; i++) {
 String str = br.readLine();
 map.put(str, map.getOrDefault(str, 0) + 1);
 }
 int K = Integer.parseInt(br.readLine());
 br.close();
 System.out.println(calculate(map, M, K));
 }
 private static int calculate(Map<String, Integer> map, int M, int K) {
 List<String> list = new ArrayList<>(map.keySet());
 list.sort((o1, o2) -> Integer.compare(map.get(o2), map.get(o1)));
 for (String s : list) {
 int zeroCount = 0;
 for (int i = 0; i < M; i++) {
 if (s.charAt(i) == '0') zeroCount++;
 }
 if (zeroCount > K) continue;
 if (zeroCount == 0) {
 if (K % 2 == 0) return map.get(s);
 continue;
 }
 if (K % zeroCount == 0 && (K / zeroCount) % 2 == 1) return map.get(s);
 }
 return 0;
 }
}

kjh95828 1년 전 0

버튼은 중복 가능하게 누를 수 있으므로, zeroCount + 2n = k면 됩니다

ex) 00110
zeroCount = 3
가능한 K의 수 = 3, 5, 7, 9...
작성자님의 논리에서 가능한 K의 수 = 3, 9, 15....
00110에서의 경우의 수
1. 각각 1, 2, 5번째 열의 버튼을 누르면 일단 해당 행의 모든 불이 켜짐 : 최소로 필요한 버튼 누르는 수 3회
2. 이후 아무 버튼이나 두 번 누르면 모든 불이 켜진 상태를 유지할 수 있음
ex) 00110 에서 1, 2, 5, 1, 1번째 열 버튼을 누르면 11111 상태가 됨

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC